JZ52 两个链表的第一个公共节点

题目描述

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

当不存在公共节点时，返回空节点。

数据范围：

• 链表长度 [1,30000]
• 保证两个链表不完全相同，即两链表的头结点不相同

示例

给出两个链表如下所示：
A：        a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

输出第一个公共节点c1

解题思路

方法一：双指针法（推荐）

核心思想： 两个指针分别遍历两个链表，当一个指针到达末尾时，让它从另一个链表的头部重新开始。这样两个指针最终会同时到达公共节点（如果存在）或同时到达null（如果不存在公共节点）。

关键洞察：

• 假设链表A长度为m，链表B长度为n
• 链表A独有部分长度为a，链表B独有部分长度为b，公共部分长度为c
• 则有：m = a + c，n = b + c
• 指针pA走过的路径：a + c + b，指针pB走过的路径：b + c + a
• 两者路径长度相同：a + c + b = b + c + a

时间复杂度： O(m + n)
空间复杂度： O(1)

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }
    
    pA, pB := headA, headB
    
    for pA != pB {
        if pA == nil {
            pA = headB
        } else {
            pA = pA.Next
        }
        
        if pB == nil {
            pB = headA
        } else {
            pB = pB.Next
        }
    }
    
    return pA
}

我来详细解释这个找两个链表交点的算法，它使用了一个非常巧妙的双指针技巧。

算法核心思想

让两个指针走过相同的总距离，从而在交点相遇。

为什么这个方法有效？

情况1：两个链表有交点

假设：

• 链表A长度：a + c（a是A独有部分，c是公共部分）
• 链表B长度：b + c（b是B独有部分，c是公共部分）

链表A: A1 -> A2 -> A3 -> C1 -> C2 -> C3
链表B:      B1 -> B2 -> C1 -> C2 -> C3
                        ↑
                     交点在这里

指针移动过程：

1. 第一轮遍历：

   • pA 走完链表A：A1 -> A2 -> A3 -> C1 -> C2 -> C3 -> null
   • pB 走完链表B：B1 -> B2 -> C1 -> C2 -> C3 -> null

2. 切换起点：

   • pA 从链表B的头开始：B1 -> B2 -> ...
   • pB 从链表A的头开始：A1 -> A2 -> A3 -> ...

3. 第二轮遍历中相遇：

   • pA 总路径：(a + c) + b = a + b + c
   • pB 总路径：(b + c) + a = a + b + c

关键洞察：两个指针走过相同的总距离 a + b + c 后，会在交点相遇！

情况2：两个链表没有交点

链表A: A1 -> A2 -> A3 -> null
链表B: B1 -> B2 -> null

• pA 总路径：a + b，最终指向 null
• pB 总路径：b + a，最终指向 null
• 两个指针同时变为 null，循环结束，返回 null

代码执行过程示例

以有交点的情况为例：

链表A: 1 -> 2 -> 8 -> 4 -> 5
链表B: 3 -> 6 -> 7 -> 8 -> 4 -> 5
                     ↑
                   交点

执行步骤：

步骤	pA位置	pB位置	pA值	pB值	说明
0	A链表	B链表	1	3	初始状态
1	A链表	B链表	2	6	正常前进
2	A链表	B链表	8	7	正常前进
3	A链表	B链表	4	8	正常前进
4	A链表	B链表	5	4	正常前进
5	A链表	B链表	null	5	pA到达A链表末尾
6	B链表	B链表	3	null	pA切换到B链表，pB到达B链表末尾
7	B链表	A链表	6	1	pB切换到A链表
8	B链表	A链表	7	2	继续前进
9	B链表	A链表	8	8	相遇！找到交点

图解可视化

第一阶段：各自遍历自己的链表
pA: 1 -> 2 -> 8 -> 4 -> 5 -> null
pB: 3 -> 6 -> 7 -> 8 -> 4 -> 5 -> null

第二阶段：切换到对方链表
pA: null -> 3 -> 6 -> 7 -> 8 (在这里相遇!)
pB: null -> 1 -> 2 -> 8 (在这里相遇!)

总距离都是：3 + 3 = 6 步到达交点

算法优势

1. 时间复杂度：O(m + n) - 每个节点最多访问2次
2. 空间复杂度：O(1) - 只用了两个指针
3. 代码简洁：无需计算链表长度或使用额外存储空间

关键理解点

1. 距离相等原理：通过让两个指针都走 链表A长度 + 链表B长度 的距离，消除了两个链表的长度差异。

2. 自动对齐：当短链表的指针切换到长链表时，长链表的指针已经"走掉"了长度差，实现了自动对齐。

3. 优雅处理边界：无论是否有交点，算法都能正确处理，有交点就返回交点，无交点就返回 null。

这个算法的巧妙之处在于用时间换取了空间的节省，并且通过数学上的距离相等来保证算法的正确性。

方法二：长度差法

思路： 先计算两个链表的长度差，让长的链表先走差值步数，然后两个指针同时遍历。

时间复杂度： O(m + n)
空间复杂度： O(1)

方法三：哈希表法

思路： 遍历一个链表并将所有节点存入哈希表，然后遍历另一个链表查找第一个在哈希表中存在的节点。

时间复杂度： O(m + n)
空间复杂度： O(m) 或 O(n)

算法分析

1. 双指针法是最优解，空间复杂度最低
2. 长度差法逻辑更直观，但需要两次遍历来计算长度
3. 哈希表法空间换时间，消耗额外内存

边界情况

• 任一链表为空：返回null
• 两个链表无公共节点：最终两指针都指向null，返回null
• 公共节点就是其中一个链表的头节点
• 两个链表长度相差很大

运行测试

# 运行所有测试
go test -v

# 运行性能测试
go test -bench=.

# 运行特定测试
go test -run TestGetIntersectionNode

相关题目

• 剑指Offer 35 - 反转链表
• LeetCode 160 - 相交链表

标签

链表 双指针 简单