剑指offer 面试题52. 两个链表的第一个公共节点（易）

考查应聘者对时间复杂度和空间复杂度的理解及分析能力。解决这道题有多种不同的思路。每当应聘者想到一种思路的时候，都要很快分析出这种思路的时间复杂度和空间复杂度各是多少，并找到可以优化的地方。

Question

输入两个链表，找出它们的第一个公共节点。

如下面的两个链表：

160_statement

在节点 c1 开始相交

示例 1：

160_example_1 
1
2
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8

输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

160_example_2 
1
2
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2

输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

160_example_3 
1
2
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null

输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 解释：这两个链表不相交，因此返回 null。

注意： 如果两个链表没有交点，返回 null. 在返回结果后，两个链表仍须保持原有的结构。 可假定整个链表结构中没有循环。 程序尽量满足 \(O(n)\) 时间复杂度，且仅用 \(O(1)\) 内存。

测试用例

功能测试（输入的两个链表有公共节点：第一个公共节点在链表的中间，第一个公共节点在链表的末尾，第一个公共节点是链表的头节点；输入的两个链表没有公共节点）。 特殊输入测试（输入的链表头节点是 nullptr 指针）。

本题考点

考查应聘者对时间复杂度和空间复杂度的理解及分析能力。解决这道题有多种不同的思路。每当应聘者想到一种思路的时候，都要很快分析出这种思路的时间复杂度和空间复杂度各是多少，并找到可以优化的地方。 考查应聘者对链表的编程能力。

Intuition

基于链表翻转

将两条链表翻转过来，然后从新链表的head往后移动指针，直到第一个后续节点不一样的节点，就是之前链表的公共节点，链表翻转可以在 \(O(n)\) 的时间复杂度内完成。假设两条链表的长度分别为 \(O(n)\) 和 \(O(m)\)。则该算法的时间复杂度为 \(O(n+m)\)，空间复杂度为 \(O(1)\)。

基于栈

分别把两个链表的节点放入两个栈里，这样两个链表的尾节点就位于两个栈的栈顶，接下来比较两个栈顶的节点是否相同。如果相同，则把栈顶弹出接着比较下一个栈顶，直到找到最后一个相同的节点。该算法的时间复杂度为 \(O(n+m)\)，空间复杂度由于需要辅助栈，所以是 \(O(m+n)\)。

快慢指针

首先遍历两个链表得到它们的长度，就能知道哪个链表比较长，以及长的链表比短的链表多几个节点。在第二次遍历的时候，在较长的链表上先走若干步，接着同时在两个链表上遍历，找到的第一个相同的节点就是它们的第一个公共节点。该算法的时间复杂度为 \(O(n+m)\)，空间复杂度由于不需要辅助栈，所以是 \(O(1)\)。三种方法中，这种实现简单，时间、空间开销都比较小。

相交链表

我们通常做这种题的思路是设定两个指针分别指向两个链表头部，一起向前走直到其中一个到达末端，另一个与末端距离则是两链表的 长度差。再通过长链表指针先走的方式消除长度差，最终两链表即可同时走到相交点。

换个方式消除长度差： 拼接两链表。 设长-短链表为的表头指针为C，短-长链表的表头指针为D（分别代表长链表在前和短链表在前的拼接链表），则当 C 走到长短链表交接处时，D 走在长链表中，且D与长链表头距离为长度差;

以下图片帮助理解：当 ha == hb 时跳出，返回即可

5651993ddb76ae6a42f0b338aec9382206f567041113f49d6ca670832ac75791-Picture1

该算法的时间复杂度为 \(O(2m-n)\)，\(m>n\)；空间复杂度由于不需要辅助栈，所以是 \(O(1)\)。

作者：Krahets 链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/intersection-of-two-linked-lists-shuang-zhi-zhen-l/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
    def getLength(self, head):
        if head == None: return 0
        p = head
        count = 0
        while p:
            count += 1
            p = p.next
        return count

    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        A_len = self.getLength(headA)
        B_len = self.getLength(headB)
        residual = abs(A_len - B_len)
        print(A_len)
        print(B_len)
        print(residual)

        p_A = headA
        p_B = headB
        
        # 开始快慢指针
        if A_len > B_len:
            while residual:
                p_A = p_A.next
                residual -= 1
        else:
            while residual:
                p_B = p_B.next
                residual -= 1
        
        # 开始寻找公共节点
        while p_A and p_B:
            if p_A == p_B:  # 这里不能用p_A.val == p_B.val
                return p_A
            else:
                p_A = p_A.next
                p_B = p_B.next
  • 交叉链表方法
1
2
3
4
5
6
7
class Solution(object):
    def getIntersectionNode(self, headA, headB):
        ha, hb = headA, headB
        while ha != hb:
            ha = ha.next if ha else headB
            hb = hb.next if hb else headA
        return ha