求相同后缀起始位置：2012年408算法题

题目

算法思想

  1. 分别求出两个链表的长度len1和len2
  2. 将两个链表以表尾对齐：令指针 p、q 分别指向 str1 和 str2 的头结点，根据len1和len2的长度大小，使指针 p 和 q 所指的结点到表尾的长度相等
  3. 反复将指针 p 和 q 同步向后移动，并判断它们是否指向同一结点。若 p 和 q 指向同一结点，则该点即为所求的共同后缀的起始位置

算法实现

int LengthOfList(Node* L) {
	int len = 0;
	while (L->next != NULL) {
		L = L->next;
		len++;
	}
	return len;
}

Node* findCommonSuffix(Node* L1, Node* L2) {
	int len1 = LengthOfList(L1);
	int len2 = LengthOfList(L2);
	Node* p, * q;
	for (p = L1;len1 > len2 ; len1--)
	{
		p = p->next;
	}
	for (q = L2; len1 < len2; len2--)
	{
		q = q->next;
	}

	while(p!=NULL && p!=q)
	{
		p = p->next;
		q = q->next;
	}
	return p;
}

时间复杂度

时间复杂度为：O(len1+len2)，其中 len1、len2 分别为两个链表的长度。即求两个链表长度的时间复杂度之和