LeetCode 160：相交链表

题目描述

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null。

题目的关键点有两个：

1. 这里说的“相交”，指的是两个链表从某个节点开始，后面的节点全部共用，而不是节点值相同。

2. 要返回的是相交的那个节点本身，不是相交节点的值。

示例分析

假设有下面这样两个链表：

可以看到，链表 A 和链表 B 在节点 8 处相交。

所以最终应该返回这个相交节点。

如果两个链表像下面这样：

A: 2 -> 6 -> 4
B: 1 -> 5

那么它们没有公共节点，应该返回 null。

解题思路

这道题最经典的做法就是双指针。

我们定义两个指针：

• A 从链表 headA 出发

• B 从链表 headB 出发

然后两个指针每次都向后移动一个节点。

关键规则

• 如果指针 A 走到了链表 A 的末尾，那么它就切换到链表 B 的头节点继续走。

• 如果指针 B 走到了链表 B 的末尾，那么它就切换到链表 A 的头节点继续走。

最后，当 A == B 时，循环结束。

此时有两种情况：

1. 两个指针在相交节点相遇，返回该节点

2. 两个指针都走到 null，说明两个链表不相交，返回 null

为什么这样做是对的

这道题最难理解的地方，不是代码怎么写，而是为什么两个指针切换链表后就一定能相遇。

情况一：两个链表相交

假设：

• 链表 A 长度为 a + c

• 链表 B 长度为 b + c

其中：

• a 表示链表 A 在相交点之前的长度

• b 表示链表 B 在相交点之前的长度

• c 表示相交后的公共长度

那么：

• 指针 A 先走 a + c 步到达链表 A 末尾，再切换到链表 B，继续走 b 步到达相交点

• 指针 B 先走 b + c 步到达链表 B 末尾，再切换到链表 A，继续走 a 步到达相交点

也就是说：

• A 一共走了 a + c + b

• B 一共走了 b + c + a

两者走的总长度是一样的，所以它们一定会在相交点相遇。

情况二：两个链表不相交

如果两个链表没有交点，那么：

• 指针 A 会走完 A，再走完 B，最后到达 null

• 指针 B 会走完 B，再走完 A，最后到达 null

两者也会在同一时刻变成 null，循环结束，返回 null。

所以这种方法不需要提前计算链表长度，也不需要额外空间，思路非常巧妙。

代码实现

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        while (A != B) {
            if (A != null) A = A.next;
            else A = headB;
​
            if (B != null) B = B.next;
            else B = headA;
        }
        return A;
    }
}

代码解析

1. 定义两个指针

ListNode A = headA, B = headB;

两个指针分别从两个链表的头节点开始出发。

2. 当两个指针不相等时继续循环

while (A != B) {

这里比较的是节点引用，不是节点值。

也就是说，只有当两个指针指向同一个节点对象时，才说明它们真正相遇了。

3. 指针 A 的移动逻辑

if (A != null) A = A.next;
else A = headB;

如果 A 还没有走到末尾，就继续往后走一步。

如果 A 已经走到链表末尾了，就切换到链表 B 的头节点。

4. 指针 B 的移动逻辑

if (B != null) B = B.next;
else B = headA;

B 的逻辑和 A 完全对称。

5. 返回结果

return A;

循环结束时，A == B。

如果有交点，这里返回的是相交节点。 如果没有交点，这里返回的是 null。

执行过程模拟

我们还是看这个例子：

A: 4 -> 1 -> 8 -> 4 -> 5
B: 5 -> 6 -> 1 -> 8 -> 4 -> 5

两个指针的移动过程大致如下：

A: 4 -> 1 -> 8 -> 4 -> 5 -> null -> 5 -> 6 -> 1 -> 8
B: 5 -> 6 -> 1 -> 8 -> 4 -> 5 -> null -> 4 -> 1 -> 8

最终它们会在节点 8 处相遇。

这就是因为两个指针都走了同样长的路径：

• A 走了 A 链表 + B 链表

• B 走了 B 链表 + A 链表

路径总长度一致，因此会在同一点相遇。

为什么不能只比较节点值

有些同学第一次做这题时，可能会想到比较两个链表中节点的值是否相同。

这是不对的。

因为题目要求的是链表节点相交，也就是两个链表从某个节点开始共享同一段内存地址，而不是单纯数值相同。

例如：

A: 1 -> 2 -> 3
B: 4 -> 5 -> 3

虽然两个链表最后一个节点的值都为 3，但如果它们不是同一个节点对象，就不能算相交。

所以这题必须比较节点引用，而不是值。

复杂度分析

时间复杂度

O(m + n)

其中：

• m 是链表 A 的长度

• n 是链表 B 的长度

每个指针最多走两遍链表，总体仍然是线性时间复杂度。

空间复杂度

O(1)

只使用了两个指针，没有使用额外的数据结构。

和哈希表解法对比

这道题还有一种比较直接的做法，就是先把链表 A 的所有节点存到哈希表中，然后再遍历链表 B，看哪个节点第一次出现在哈希表里。

哈希表做法

• 先遍历 A，把所有节点放进 HashSet

• 再遍历 B，判断当前节点是否已经在集合中

• 如果在，说明找到了交点

• 如果遍历结束还没找到，说明不相交

对比

双指针解法

优点：

• 不需要额外空间

• 思路巧妙，代码简洁

缺点：

• 第一次接触时不太容易想到

哈希表解法

优点：

• 思路直接，容易理解

缺点：

• 需要额外的 O(m) 空间

所以这道题更推荐使用双指针解法。

总结

这道题的核心在于：

1. 两个指针分别从两个链表出发

2. 走到末尾后切换到对方链表继续走

3. 这样两个指针最终会走过相同的总长度

4. 如果有交点，就会在交点相遇

5. 如果没有交点，就会同时走到 null

这是一道非常经典的链表双指针题，代码不长，但思想非常巧妙。 只要把“两个指针最终走过的总长度相同”这个核心点想明白，这道题就不难了。