求单链表交点

题目

今天面试时,面试官问了这样一个问题:两个单链表相交,怎么求交点。所谓相交,就是两个节点的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,还是要多刷题啊!

算法

上一篇 memset的一个坑
下一篇 N-sum问题通解

添加新评论

*
*