假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading”和“being”的存储映像如下图所示。
设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为 
1）给出算法的基本设计思想。
2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度。
[问答题]
问题信息
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
顺序遍历两个链表到尾结点时，并不能保证两个链表同时到达尾结点。这是因为两个链表的长度不同。假设一个链表比另一个链表长k个结点，我们先在长链表上遍历k个结点，之后同步遍历两个链表，这样就能够保证它们同时到达最后一个结点。由于两个链表从第一个公共结点到链表的尾结点都是重合的，所以它们肯定同时到达第一个公共结点。
算法的基本设计思想：
① 分别求出str1和str2所指的两个链表的长度m和n。
② 将两个链表以表尾对齐：令指针p、q分别指向str1和str2的头结点，若m>=n，则使p指向链表中的第m-n+1个结点；若m<n，则使q指向链表中的第n-m+1个结点，即使指针p和q所指的结点到表尾的长度相等。
③ 反复将指针p和q同步向后移动，并判断它们是否指向同一结点。若p和q指向同一结点，则该点即为所求的共同后缀的起始位置。
2）算法的C语言代码描述：
LinkNode *Find_1st_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<len2;len2--) //使q指向的链表与p指向的链表等长 q=q->next; while(p->next!=NULL&&p->next!=q->next){ //查找共同后缀起始点 p=p->next; //两个指针同步向后移动 q=q->next; } return p->next; //返回共同后缀的起始点 }【1）、2）的评分说明】 ①若考生所给算法实现正确，且时间复杂度为O(m+n)，可给12分；若算法正确，但时间复杂度超过O(m+n)，则最高可给9分。
② 若在算法的基本设计思想描述中因文字表达没有非常清晰反映出算法思路，但在算法实现中能够清晰看出算法思想且正确的，可参照①的标准给分。
③ 若算法的基本设计思想描述或算法实现中部分正确，可参照①中各种情况的相应给分标准酌情给分。
3）时间复杂度为：O(len1+len2)或O(max(len1,len2))，其中len1、len2分别为两个链表的长度。
【3）的评分说明】 若考生所估计的时间复杂度与考生所实现的算法一致，可给1分。