160. 相交链表

题目

力扣题目

给定两个无环单链表的头节点 headA 和 headB，找出并返回它们相交的起始节点；若不相交，返回 nullptr。函数返回后不能改变原链表结构。

链表相交指两个指针指向同一个节点对象，而不是节点值相同。

示例：

A：4 → 1 ↘
           8 → 4 → 5
B：5 → 6 → 1 ↗

输出：值为 8 的共享节点

提示：

• 两个链表均非空，节点数最多为 3 × 10^4
• 整个链式结构中不存在环
• 进阶要求 $O(m+n)$ 时间、$O(1)$ 额外空间

考察内容

• 节点地址与节点值的区别
• 两个链表长度差的消除
• 双指针切换链表头
• 不相交时的统一终止条件
• 保持原链表结构不变

解题思路

双指针切换链表

令 pa、pb 分别从 headA、headB 出发，每次向后移动一个节点：

• pa 走到链表 A 末尾后，切换到 headB；
• pb 走到链表 B 末尾后，切换到 headA。

假设 A 的独有前缀长度为 a，B 的独有前缀长度为 b，公共尾部长度为 c。两个指针分别走过：

pa：A 的 a+c，再走 B 的 b
pb：B 的 b+c，再走 A 的 a

两条路径长度都为 a + b + c，因此长度差被交换链表头自动抵消，两个指针会同时到达第一个公共节点。

若链表不相交，两个指针都走完 m+n 个节点后同时变为 nullptr，循环同样能够正常结束。

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

长度对齐法

也可以先分别计算两个链表长度，让较长链表的指针先移动长度差，再同步前进。原理相同，但需要额外的长度计算代码；切换链表头的写法更紧凑。

代码演示

struct ListNode {
    int val;
    ListNode* next;

    explicit ListNode(int value = 0, ListNode* nextNode = nullptr)
        : val(value), next(nextNode) {}
};

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    ListNode* pa = headA;
    ListNode* pb = headB;

    while (pa != pb) {
        pa = (pa == nullptr) ? headB : pa->next;
        pb = (pb == nullptr) ? headA : pb->next;
    }

    return pa;
}

易错点

• 比较节点值而不是指针：值相同不代表相交，必须判断 pa == pb。
• 指针到末尾后继续取 next：应先判断是否为 nullptr，再决定切换或前进。
• 只让一个指针切换链表：两个指针都必须走完 A 与 B，才能消除长度差。
• 漏掉不相交情况：不相交时两者最终同时为 nullptr，应允许循环因此结束。
• 修改链表以做标记：题目要求保持原结构，双指针无需改动任何 next。
• 通过值序列判断共享尾部：即使两个链表尾部的值完全相同，也可能是不同节点对象。

总结

让两个指针分别走 A+B 和 B+A，就能把两个链表的长度差放到路径的不同位置抵消。最终它们要么在第一个共享节点相遇，要么同时到达空指针。

相关题目

• 141. 环形链表
• 142. 环形链表 II
• 19. 删除链表的倒数第 N 个结点
• 876. 链表的中间结点