160. 相交链表（Intersection of Two Linked Lists）

频次 ★★★ · 难度 🟢 · 高频：快手

题目

给定两个单链表的头节点 headA、headB，找到它们相交的起始节点；如果不相交返回 null。要求 O(1) 额外空间。

示例：

A: 4 -> 1 -> 8 -> 4 -> 5
B:      5 -> 6 -> 1 -> 8 -> 4 -> 5   (从节点 8 开始与 A 共享)
输出: 节点 8

思路

两条链表长度可能不同，但如果相交，从相交点到各自末尾的部分是完全一样的。双指针走”补齐路径”：pA 走完 A 后接着走 B，pB 走完 B 后接着走 A。这样两个指针走过的总长度都是 |A| + |B|，如果相交，它们会在相交点相遇；如果不相交，两者会同时到达 null（此时 pA == pB == null，循环退出返回 null，逻辑统一不用特判）。

代码

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return null;
    }
    ListNode pA = headA, pB = headB;
    while (pA != pB) {
        pA = (pA == null) ? headB : pA.next;
        pB = (pB == null) ? headA : pB.next;
    }
    return pA;
}

复杂度

• 时间：O(m + n) — m、n 分别是两条链表长度
• 空间：O(1)

边界条件

• 两条链表不相交：pA、pB 各自走完”自己 + 对方”的长度后同时变为 null，pA == pB（都是 null）成立，循环退出返回 null，天然正确。
• 其中一条链表为空：headA == null || headB == null 直接返回 null（空链表不可能与任何链表相交）。
• 两条链表完全重合（从头就相交）：第一轮遍历就会在起点相遇，返回 headA（也就是 headB）。

变式

• 已知两条链表长度：可以先让长链表的指针前进”长度差”步，再同步遍历比较节点引用，效果和双指针法一样，只是需要先算长度（多一轮遍历）。
• 判断两条链表是否相交（不需要找到具体节点）：可以比较两条链表的尾节点是否相同（相交的链表尾节点一定相同），比找交点更简单。

易错点

• 判断相交要用 pA == pB（节点引用相等），不能用 pA.val == pB.val（值相同但可能是不同节点）。
• 不相交时两指针最终都会变成 null 并退出循环，不需要额外判断”永远走不到一起”的死循环风险。

面试追问

• “走完自己的链表再走对方的链表”这个技巧的本质是什么？ 本质是用路径拼接的方式抹平两条链表的长度差：设两条链表长度分别是 m、n，相交部分长度为 c，两个指针最终都走了 m + n 步，如果相交，走到第 m+n-c 步时必然位于同一节点（交点），如果不相交，两者会同时在第 m+n 步到达 null。
• 如果不允许修改链表、也不允许用额外空间，还有别的思路吗？ 双指针法本身就满足这两个约束；如果放宽约束，可以用 HashSet 记录一条链表的所有节点，遍历另一条链表时检查是否命中，是更直观但需要 O(m) 额外空间的做法。

关联题

• 同套路：141. 环形链表I、142. 环形链表II —— 双指针相遇家族，本题靠换轨补齐路程差
• 进阶：两条链表都可能有环时求交点 —— 本题与 142 的组合应用
• 知识点：a+c+b = b+c+a 的等式思维——把”对齐”转化为”走同样总路程”，不用先算长度