求单链表交点

题目

今天面试时，面试官问了这样一个问题：两个单链表相交，怎么求交点。所谓相交，就是两个节点的next指针相同。

简单解法

一个简单的思路是：分别遍历这两个链表，并将这两个链表的节点分别保存到两个列表里，然后同步逆序遍历这两个列表，当出现不相同的元素时，则下一个元素就是这两个链表的交点。

例如，对于上图的两个单链表，遍历上面的单链表得到列表：A, B, C, D, E, F, G；遍历下面的单链表得到列表：H, I, E, F, G。因为单链表相交之后就汇合了，汇合之后的节点就是一样的，而汇合之前的节点不一样，所以同步逆序遍历这两个列表：G-G, F-F, E-E, D-I……于是，E节点就是交点。

这种做法时间复杂度为$O(n)$，但空间复杂度为$O(n)$，有没有空间复杂度更低的解法呢？

如果使用HashMap存储，先遍历上面的单链表，并把节点存储到HashMap里，然后遍历下面的单链表，每次都看当前节点是否已经存在于HashMap中，如果存在，则该节点就是交点。采用这种做法，不必把两个单链表都遍历完，不过依然没有降低空间复杂度。

另一种思路是暴力法，也就是遍历这两个链表，判断第一个链表的每个节点是否在第二个链表中，这种做法的时间复杂度为$O(n^2)$。

优雅解法

这个问题比较麻烦的地方在于，这两个单链表相交之前的部分的长度可能不一致。假如这两个单链表长度一致，那么指针p、q只要同步移动，然后首次相遇的地方就是交点了。

例如，对于图中的两个单链表，假如上面的单链表没有A, B节点，指针p初始指向C节点，那么，指针p、q只要同步移动两次，就会在节点E相遇，E节点就是交点。那么，我们要怎么样让指针p指向C节点后，指针p、q才同步移动呢？

其实很简单，先遍历一下这两个单链表，得到它们的长度，然后让长的单链表的指针先走长度之差步，就可以了！对于图中的两个单链表，上面的单链表长度为7，下面的单链表长度为5，两个单链表的长度之差为2，且上面的单链表更长，那么就让指针p先走2步（这样就到了C节点），然后指针p、q同步移动即可。

扩展问题

如何判断两个单链表是否相交

这个问题比较简单。显然，如果两个单链表相交，则必然是“Y”形的，而不是“X”形的。只需要判断两个单链表中是否存在相同的元素即可。

如果这两个单链表相交，则尾节点必然相同，因此，直接遍历到尾节点，然后判断尾节点是否相同即可。还可以把节点存到哈希表，在遍历第二个单链表时，判断节点是否在哈希表中已存在，若已存在则相交。

如何判断单链表里是否有环

这个可以采用快慢指针的技巧。初始时，指针p、q都位于初始节点，然后每次指针p移动一个节点，指针q移动两个节点，则指针p、q必然在环内相遇。

为什么指针p、q必然在环内相遇呢？这是因为在环内，可以看成是指针q“追赶”指针p，每次“追赶”1一个节点（也就是相对距离-1），所以必然能相遇。而且，指针p、q相遇时，指针p在环内走过的距离不会超过环的长度。

LeetCode: 141. Linked List Cycle

如何求单链表的环的长度

很简单：根据上一个问题可以知道一个处于环内的节点，固定指针q，然后继续移动指针p（指针p每次移动一个节点），当指针p、q再次相遇时，指针p继续移动的次数就是环的长度。

如何求单链表中第一个在环里的节点

假设单链表起点到第一个在环里的节点的距离为$n$，快慢指针p、q在环内相遇，第一个在环里的节点到相遇点的距离为$f$，环的长度为$L$。

那么，显然，指针p、q相遇时，指针p走过的距离为$n+f$，指针q走过的距离为$n+f+xL$（之所以是$xL$是因为，假如$n$较大而$L$较小，那么指针q可能在环内转了好几圈才和指针p相遇）。显然有：

$2(n+f) = n+f+xL$

故 $n = xL-f, x>0$，或者写为：

$n = L - f + xL \quad x\geq0$

而指针p、q的相遇点到第一个在环里的节点的距离为$L-f$。指针p从单链表的起点开始移动，每次移动1个节点，指针q从相遇点开始移动，每次也移动1个节点，那么，指针p、q就会在第一个在环里的节点处相遇。

LeetCode: 142. Linked List Cycle II

特殊解法

对于本文最开始的问题，还有一种比较特殊的解法。先遍历其中一个链表，遍历到尾节点时，将尾节点的next指针指向另一个链表的起点，然后，问题就转化为求单链表中第一个在环里的节点了。

后记：

在LeetCode上刷到了原题：160. Intersection of Two Linked Lists，还是要多刷题啊！