【题目】
42.(13分)假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading”和“being”的存储映像如下图所示。
设strl和str2分别指向两个单词所在单链表的头结点，链表结点结构为
，请设计一个时间上尽可能高效的算法，找出由str1和str2所指的两个链表共同后缀的起始位置(如图中字符i所在结点的位置p)。要求：
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C或c++或Java语言描述算法，关键之处给出注释。
(3)说明你所设计算法的时间复杂度。
【答案要点】
(1)给出算法的基本设计思想：(4分)
①分别求出str1和str2所指的两个链表的长度m和n;
②将两个链表以表尾对齐：令指针p、q分别指向str1和str2的头结点，若m≥n，则使p指
向链表中的第m-n+1个结点;若m
指的结点到表尾的长度相等。
③反复将指针p和q同步向后移动，并判断它们是否指向同一结点。若p和q指向同一结点，
则该点即为所求的共同后缀的起始位置。
(2)算法实现：(8分)
typedef struct Node{
char data;
struct Node*next;
}SNODE;
SNODE*findlist(SNODE*str1，SNODE*str2){
int m，n;
SNODE*p，*q;
m=listlen(str1); /*求str1的长度。0(m)*/
n=listlen(str2); /$求str2的长度。0(n)*/
/*以下3个循环的时间复杂度为：0(max(m，n))*/
for(p=str1;m>“;m--) /*使p指向的链表与q指向的链表等长*/
p=p->next;
for(q=str2;m<n;n--) p="" <="">
q=q->next;
while(p->next!=NULL&&p->next!=q->next){
/*查找共同后缀起始点*/
p=p->next; /*两个指针同步向后移动*/
q=q->next;
}
return p->next; /*返回共同后缀的起始点*/
}
int listlen(SNODE*head){ /*求链表长度*/
int len=0：
while(head->next!=NULL){
len*+;
head=head->next;
}
return len;
}
(3)说明算法的时间复杂度：(1分)
参考答案的时间复杂度为：0(m+rt)或0(max(m，n))。其中m、n分别为两个链表的长度。