用单链表保存单词，两个单词的相同后缀共享存储空间，找出后缀起始位置

问题描述：

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

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

1)给出算法的基本设计思想。

2)根据设计思想，用C或C++或Java语言描述算法，关键之处给出注释。

3)说明你所设计算法的时间复杂度。

问题解答：

本题的结构体是单链表，用双指针法。用指针p、q分别扫描strl和str2,当p、q指向同一个地址时，即找到共同后缀的起始位置。

1)算法的基本设计思想如下：

• ①分别求出strl和str2所指的两个链表的长度m和n。
• ②将两个链表以表尾对齐：令指针p、q分别指向strl和str2的头结点，若m>=n，则指针P先走，使p指向链表中的第m-n+1个结点；若m<n,则使q指向链表中的第n-m+1 个结点，即使指针p和q所指的结点到表尾的长度相等。
• ③反复将指针p和q同步向后移动，当p、q指向同一位置时停止，即为共同后缀的其实位置，算法结束。

2)本题代码如下：

typedef struct Node{
    char data;
    struct Node *next;
}SNode;
/*求链表长度的函数*/
int listlen(SNode *head){
    int len=0;
    while(head->next!=NULL){
        len++;
        head=head->next;
    }
    return len;
}
/*找出共同后缀的起始地址*/
SNode* find_addr(SNode *strl,SNode *str2){
    int m,n;
    SNode *p, *q;
    m=listlen (strl) ;  //求 strl 的长度
    n=listlen (str2) ;  //求 str2 的长度
    for (p=str1;m>n;m--) //若m>n，使p指向链表中的第m-n+1个结点
        p=p->next;
    for (q=str2;m<n;n--) //若m<n,使q指向链表中的第n-m+l个结点
        q=q->next;
    while (p->next !=NULL && p->next!=q->next) {
        //将指针 p 和 q 同步向后移动
        p=p->next;
        q=q->next;
    }//while
    return p->next; //返回共同后缀的起始地址
}