（13 分）假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，
例如，“loading”和“being”的存储映像如下图所示。

设 str1 和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为
，请设计一个时间上尽 可能高效的算法，找出由 str1 和 str2 所指向两个链表共同后缀的起始位置（如图中字符 i 所在结点的位置 p）。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用 C 或 C++或 JAVA 语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时间复杂度。

（1）算法思想：顺序遍历两个链表到尾结点时，并不能保证两个链表同时到达尾结点。这是因为两个链表的长度不同。假设一个链表比另一个链表长 k 个结点，我们先在长链表上遍历 k 个结点，之后同步遍历两个链表。这样我们就能够保证它们同时到达最后一个结点了。由于两个链表从第一个公共结点到链表的尾结点都是重合的。所以它们肯定同时到达第一个公共结点。于是得到算法思路：
① 遍历两个链表求的它们的长度 L1，L2；
② 比较 L1，L2，找出较长的链表，并求 L=|L1-L2|；
③ 先遍历长链表的 L 各结点；
④ 同步遍历两个链表，直至找到相同结点或链表结束。
（2）算法的 C 语言代码描述
LinkList Search_First_Common(LinkList L1,LinkList L2){
//本算法实现线性时间内找到两个单链表的第一个公共结点
int len1=Length(L1);,len2=Length(L2);
LinkList longList,shortlist;//分别指向较长和较短的链表
if(len1>len2){
longList=L1->next;
shortlist=L2->next;
L=len1-len2;//表长之差
}
else{
longList=L2->next;
shortlist=L1->next;
L=len2-len1;//表长之差
}
While(L--)
longList=longList->next;
while(longList!=NULL){
if(longList==shortList)//同步寻找共同结点
return longList;
else{
longList=longList->next;
shortlist=shortlist->next;
}
}//while
return NULL;
}
（3）算法的时间复杂度为 O(len1+len2)，空间复杂度为 O(1)。