设计一个算法，找出由str1和str2所指向两个链表共同后缀的起始位置

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

设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为 datanext ，请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置（如图中字符i所在的结点位置p）。

方法一：暴力

思想：外层循环遍历str1，内存循环遍历str2，遍历过程中比较是否相等。

代码：

typedf char ElemType;
typedf struct LNode {ElemType data;struct LNode *next;
}LNode,*LinkList;
LinkList getsameNode(LinkList L1,LinkList L2){L1=L1->next;while(L1!=NULL){//外层循环L1 LNode *p=L2->next;while(p!=NULL){//内存循环L2 if(L1==p){return L1;}p=p->next;}L1=L1->next;}//没找到 return NULL;
}

时间复杂度O（len1+len2）；空间复杂度O（1）

方法二：让较长的链表先移动，直到两个链表长度一样时，进行同时移动。

思想：分别求两个链表长度。然后对较长的那个链表先进行遍历，直到两个链表相同时，进行同时遍历，直到找到公共结点为止。

代码：

int length(LinkList L){//计算链表长度 int len=0;L=L->next;while(L!=NULL){len++;L=L->next;}return len;
}
LinkList getsameNode(LinkList L1,LinkList L2){//计算链表长度int len1=length(L1);int len2=length(L2);for(p=L1;len1>len2;len1--){//链表1更长时 p=p->next;}for(q=L2;len2>len1;len2--){//链表2更长时 q=q->next;}while(p->next!=NULL && p->next!=q->next){//此时两个链表一样长，进行差查第一个公共节点 p=p->next;q=q->next;}return p->next;//返回查找到的结点 
}

时间复杂度O（len1+len2），空间复杂度O（1）