架构师训练营第八周”性能优化二“作业

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

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

A：

先一次遍历两个链表，算出每个链表长度，同时记录最后一个元素

如果最后一个元素不同，则链表没有合并，返回

再次遍历链表，长链表先遍历，提前走 n 步(链表长度差)

同时往后遍历，直到节点相同为止

总共遍历两次，复杂度 o(n)

1. 遍历链表 1，到最后一个元素 z_1 为止，同时记录链表长度 len_1

2. 遍历链表 2，到最后一个元素 z_2 为止，同时记录链表长度 len_2

3. if z_1 ！= z_2：

4. return None; // 链表没有合并

5. c_1 = a; c_2 = d; // c_1, c_2 表示当前遍历节点，初始化指向链表头部

6. if len_1 > len_2: // 如果链表 1 更长，c1 先走 len_1-len2 步

7. for i in 1 ... len_1-len2:

8. c1 = c1->next

9. elif len_2 > len1: // 如果链表 2 更长，c2 先走 len_2-len1 步

10. for i in 1...len_1-len2:

11. c2 = c2->next

12. while c1 != c2:

13. c1 = c1->next

14. c2 = c2->next

15. return c1.value