LeetCode 面试题 02.07. 链表相交

2025-07-03 HGNULB 约 8 分钟

文章信息 11 个分类 · 3 个标签

分类

LeetCode CodeTop 简单 已解决 已掌握 2-5 字节跳动 快手 百度 滴滴 程序员面试金典（第 6 版）

标签

哈希表 双指针 链表

目录 收起 展开

题目描述

✅ 面试题 02.07. 链表相交

题意分析

给两条单链表的头节点，判断它们是否共用同一段尾部；如果是，返回共用部分的第一个节点，否则返回空。

最要紧的一句约束是「相交」的定义：指的是两条链在内存中共享同一个节点对象，而不是恰好有值相等的节点。这直接决定了所有比较都必须用引用相等，任何比较 val 的写法都是错的。举个例子，两条链里各有一个值为 1 的节点，它们可能是完全不同的两个对象。

由这个定义还能推出一个重要的结构性质：单链表每个节点只有一个 next，所以一旦两条链在某个节点汇合，之后就再也分不开了。也就是说相交部分必然是一段公共后缀，不可能出现「合了又分」。

第二个信号是进阶要求：时间 $O(m + n)$、空间 $O(1)$。这堵死了「把一条链的节点全塞进哈希集合再查另一条」这种最省事的写法。

边界要想清楚三处：任一链表为空时必然无交点；两条链长度可以相差很大；两条链完全不相交时要能自然终止并返回空，而不是死循环。题目还保证链表中无环。

解法：双指针交换链表头

核心思路

先看两个基线解法。一是哈希法：把 headA 的所有节点存进集合，再沿 headB 逐个查，第一个命中的就是交点。正确且直观，但空间 $O(m)$，不满足进阶。二是长度对齐法：先各扫一遍求出两条链的长度，让长的那条先走 |m - n| 步抵消差值，然后同步前进，相等即为交点。空间是 $O(1)$ 了，但要写求长度、算差值、按大小分支走，代码分支多，白板上容易在「谁更长」这里写反。

瓶颈其实只有一个：两条链的长度差。前缀不等长，两个指针同步走就永远对不齐。长度对齐法是显式地把差值算出来消掉，那有没有办法让它自动消掉？

关键观察是：如果让指针 curA 先走完 A 再接着走 B，让 curB 先走完 B 再接着走 A，两者走过的总长度都是 m + n。设两条链的独有前缀长度分别是 a 和 b、公共后缀长度是 c（于是 m = a + c、n = b + c）。curA 到达交点时走了 a + c + b 步，curB 到达交点时走了 b + c + a 步——完全相同。换头这个动作，恰好用「多走一遍对方的前缀」抵消了长度差。

不变量是：两个指针每轮各前进一步，走过的总步数始终相等；当两者都进入公共后缀时，它们距离链尾的剩余长度也相等，因此第一次引用相等发生的位置必然就是公共后缀的起点。 若两条链不相交，可以把「空指针」看成一个虚拟的公共终点：curA 在第 m + n + 1 步、curB 也在第 m + n + 1 步同时变为空，此时 curA == curB 成立，循环退出并返回空，无需任何额外分支。

解题步骤

• 令 curA = headA、curB = headB，两个指针从各自链头出发。
• 循环条件写成 curA != curB。用引用比较而不是值比较，是题目定义决定的；同时这个条件天然兼容「两者同时为空」的收敛情形。
• 每轮先处理 curA：若它已经是空，就跳到 headB；否则正常前进一步。判空必须在解引用之前，否则走到链尾会崩。
• 同样地处理 curB：为空则跳到 headA，否则前进一步。两个指针的推进必须在同一轮里各做一次，快慢不一致会破坏「总步数相等」这个不变量。
• 注意换头的时机是「当前指针为空」，而不是「当前指针的 next 为空」。前者让指针在切换前额外经过了一次空位置，正是这一步让不相交的情形能够同时收敛到空。
• 循环结束后直接返回 curA。它要么是交点，要么是空，两种情况共用同一个出口。

以 listA = [4,1,8,4,5]、listB = [5,6,1,8,4,5]、交点是值为 8 的那个节点走一遍：把 A 的节点记作 A0..A4，B 的记作 B0..B5，其中 A2、A3、A4 与 B3、B4、B5 是同一批对象，交点是 A2（也就是 B3）。初始 curA = A0、curB = B0，引用不同。第一轮后 curA = A1、curB = B1。第二轮后 curA = A2、curB = B2，注意此时 curA 已经是交点但 curB 还没到，不能停。第三轮后 curA = A3、curB = B3，两者都在公共段里，但位置错开，引用仍不同。第四轮后 curA = A4、curB = B4。第五轮后 curA 走出 A 的末尾变成空，curB = B5。第六轮，curA 为空所以换头到 B0，curB 走出 B 的末尾变成空。第七轮，curA = B1，curB 为空所以换头到 A0。第八轮，curA = B2，curB = A1；虽然这两个节点的值都是 1，但它们是不同对象，引用比较结果为假，循环继续——这一步正是「不能比值」的活例子。第九轮，curA = B3，curB = A2，而 B3 与 A2 是同一个对象，条件不成立，循环退出，返回值为 8 的交点节点。整个过程两个指针各走了九步，完全同步。

代码实现

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;

        // 两个指针各走两条链表，总路程一致后自然消除长度差。
        while (curA != curB) {
            if (curA == null) {
                curA = headB;
            } else {
                curA = curA.next;
            }

            if (curB == null) {
                curB = headA;
            } else {
                curB = curB.next;
            }
        }

        return curA;
    }
}

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    curA := headA
    curB := headB

    // 两个指针各走两条链表，总路程一致后自然消除长度差。
    for curA != curB {
        if curA == nil {
            curA = headB
        } else {
            curA = curA.Next
        }

        if curB == nil {
            curB = headA
        } else {
            curB = curB.Next
        }
    }

    return curA
}

复杂度分析

• 时间复杂度：$O(m + n)$，其中 $m$、$n$ 是两条链的长度。相交时两个指针最多各走 a + b + c 步，不相交时最多各走 m + n + 1 步，都是两条链长度之和的量级。
• 空间复杂度：$O(1)$，只用了 curA、curB 两个指针，没有哈希集合也没有递归栈，满足进阶要求。

关键点总结

• 处理两个不等长序列的对齐问题，除了显式算差值，还可以让两者互换赛道跑满同样的总路程，让差值自动抵消。这个技巧在「两个链表求公共部分」「两个数组求同位置关系」一类题里都能复用。
• 把「不相交」看成「在虚拟的空节点处相交」，就能让正常出口和失败出口合并成同一条。凡是能把特例吸收进主逻辑的设计，都能显著减少分支和出错面。
• 换头判据必须是「指针本身为空」而不是「指针的 next 为空」。差这一步，两个指针的总步数就会差 1，不相交时会错过同时为空的时刻，直接陷入死循环。
• 引用相等和值相等是两回事。链表题里凡是涉及「同一个节点」的判定，一律用引用比较，这是题意层面的硬性要求。
• 面试视角：完整的展示顺序是哈希法（点明 $O(m)$ 空间）、长度对齐法（点明分支多）、换头法（$O(1)$ 空间且无分支），并给出 a + c + b = b + c + a 这个等式作为正确性依据。能写出这个等式，面试官基本不会再追问。
• 面试视角：常见追问是「如果链表可能有环怎么办」。要能答：先各自判环，两条链的成环状态不同则必不相交；都无环退化为本题；都有环则需比较环入口是否相同，或让一条链的入口沿环走一圈看是否遇到另一条的入口。

易错点总结

• 错误写法：循环条件写成 curA.val != curB.val。用例 listA = [4,1,8,4,5]、listB = [5,6,1,8,4,5] → 走到 curA = B2、curB = A1 时两者值都是 1，会误判为交点并返回错误节点。
• 错误写法：换头判据写成 if (curA.next == null) curA = headB;。用例两条不相交的链 [1] 和 [2] → 两个指针永远不会同时为空，条件 curA != curB 恒成立，程序陷入死循环。
• 错误写法：先判空再解引用的顺序写反，例如写成 curA = curA.next; if (curA == null) curA = headB; 且没有前置判空。用例 listA = [1] → 第二轮对空指针取 next，直接抛空指针异常。
• 错误写法：换头时切回自己的链头，写成 curA = headA。用例 listA = [4,1,8,4,5]、listB = [5,6,1,8,4,5] → 两个指针各自在自己的链上循环，长度差永远消不掉，不相交时死循环，相交时也可能永远错开。
• 错误写法：一轮里只推进其中一个指针，例如把 curB 的更新写进 else 分支。用例任意长度不等的输入 → 总步数不再相等，「同时到达交点」的推理失效，结果随机出错。
• 错误写法：给换头加计数限制，比如「最多换一次头就退出返回空」，但退出判断写在换头之后、比较之前。用例两条恰好在最后一个节点相交的链 → 在指针有机会相遇之前就提前返回空，漏判交点。
• 错误写法：认为返回值不可能为空，于是在外层直接访问返回节点的 val。用例 listA = [2,6,4]、listB = [1,5]（不相交）→ 返回空后解引用崩溃；本题无交点是合法结果。
• 错误写法：把循环条件写成 curA != null && curB != null。用例 listA = [4,1,8,4,5]、listB = [5,6,1,8,4,5]、交点为 8 → 走满五步后 curA 变成空，循环直接退出并返回空，两个指针根本没机会进入第二条链，真实交点被漏掉。
• 错误写法：用长度对齐法时把「谁先走」判反，让短链先走差值步。用例 listA 长 5、listB 长 6 → 短链提前走出末尾，同步比较阶段两个指针始终错位，交点被跳过。

相似题目

题目	难度	考察点
160. 相交链表	简单	同一模型的主站编号，可用来检验模板是否稳定
LCR 023. 相交链表	简单	同题的国内版，适合对比不同判题下的空输入约定
剑指 Offer 52. 两个链表的第一个公共节点	简单	同题换表述，重点仍是引用相等而非值相等
141. 环形链表	简单	快慢指针判环，考察相遇条件而非对齐长度
142. 环形链表 II	中等	相遇后用数学推导定位环入口，需要额外一轮同步
876. 链表的中间结点	简单	一趟遍历定位中点，考察奇偶长度下的停止条件
287. 寻找重复数	中等	把数组下标视作链表边，把找重复转成找环入口