第八周 性能优化（二） 作业 「架构师训练营 3 期」

有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。

请用代码（或伪代码）描述算法，并给出时间复杂度。

思路：

两个单向链表在某个元素合并的情况下，也就是从某个元素开始链表合并元素向下的一段内容是相同的，长度相同，内容相同。

也有可能不合并，也就是尾部没有相同的一个或一段。

实现的代码逻辑：

for(链表 1){//遍历链表 1

a//链表 1 元素

list1//a 元素及向下的链表内容

for(链表 2){//遍历链表 2

b//链表 2 元素

if(a==b){//当两链表中元素相同时

len1//a 向下的长度

len2//b 向下的长度

if(len1!=len2||len2<len1){continue;}//长度不一致或当 len2 小于 len1 继续向下判断,

list2//b 元素及向下的链表内容

if(len1==len2){

if(list1 与 list2 内容顺序相同) //找到合并的元素是当前的 a

if(list1 与 list2 内容顺序不相同){continue;}

}

}

}

时间复杂度：O(m*n)