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

设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为

问答题给出算法的基本设计思想。

【正确答案】正确答案：顺序遍历两个链表到尾结点时，并不能保证两个链表同时到达尾结点。这是因为两个链表的长度不同。假设一个链表比另一个链表长k个结点，我们先在长链表上遍历k个结点，之后同步遍历两个链表，这样就能够保证它们同时到达最后一个结点。由于两个链表从第一个公共结点到链表的尾结点都是重合的，所以它们肯定同时到达第一个公共结点。

【答案解析】

问答题根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出注释。

【正确答案】正确答案：算法的C语言代码描述： LinkNode *Find_lst_Common(LinkList str1，LinkList str2){ int len1=Length(str1)，len2=Length(str2)， LinkNode *p，*q， for(p*str1；len1＞len2；len1--)／／使p指向的链表与q指向的链表等长 p=p-＞next， for(q=str2，len1＜fen2；len2--)／／使q指向的链表与p指向的链表等长 q=q-＞next； while (p-＞next!=NuLL＆＆p-＞next!=q-＞next){／／查找共同后缀起始点 p=p-＞next；／／两个指针同步向后移动 q=q-＞next} } return p-＞next；／／返回共同后缀的起始点 }

【答案解析】

问答题说明你所设计算法的时间复杂度。

【正确答案】正确答案：程序时间复杂度为：O(len1+len2)或O(max(len1，len2))，其中len1、len2分别为两个链表的长度。

【答案解析】解析：考查链表的遍历、求表长操作。