CS-Notes 剑指 Offer 题解 52：用 O(1) 空间的双指针法求两个链表的第一个公共结点

2026-09-06 16:41:52作者：农烁颖Land

本篇基于 CS-Notes 仓库中剑指 Offer 题解的第 52 题，完整讲解"两个链表的第一个公共结点"这一经典链表问题：从题目结构特征出发，推导双指针交换头节点算法的正确性，给出可直接复用的 Java 实现，并覆盖复杂度分析、边界情形与常见面试追问。读完后你能掌握一种时间 O(a+b)、空间 O(1) 的标准解法，并理解它为什么天然兼容"两链表不相交"的退化场景。

题目描述

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

先明确一个关键结构特征：所谓"公共结点"，指的是两条链表在某个结点上汇合后共享同一条尾部。由于是单链表（每个结点只有一个 next 指针），一旦从公共结点出发，后续路径是唯一的，因此两条链表相交后的形状只能是图中所示的 Y 型，而不可能出现 X 型交叉。

用长度记号描述这一结构：

设链表 A 的长度为 a + c，链表 B 的长度为 b + c；
其中 a、b 分别是两条链表各自的非公共前缀长度，c 是尾部公共部分长度；
两条链表总长度满足恒等式 a + c + b = b + c + a。

这个看似平凡的等式，正是双指针算法的数学基础。

结点结构采用剑指 Offer 系列的通用定义：

public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

核心解法：双指针交换头节点

设两个指针 l1、l2 分别初始指向链表 A 和链表 B 的头节点。核心操作只有一条规则：

当访问链表 A 的指针走到尾部（null）时，令它从链表 B 的头部重新开始；当访问链表 B 的指针走到尾部时，令它从链表 A 的头部重新开始。这样就能控制访问 A 和 B 两个链表的指针同时到达交点。

CS-Notes 原文给出的 Java 实现如下（签名与牛客网原题一致）：

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    ListNode l1 = pHead1, l2 = pHead2;
    while (l1 != l2) {
        l1 = (l1 == null) ? pHead2 : l1.next;
        l2 = (l2 == null) ? pHead1 : l2.next;
    }
    return l1;
}

代码只有五行有效语句：l1 走完 A 就跳去走 B，l2 走完 B 就跳去走 A；循环终止条件就是"两个指针相遇"。

为什么两指针一定同时到达交点

逐段拆解 l1（从 A 头出发）在相遇前走过的路径：

先走完 A 的非公共前缀（a 步）和公共尾部（c 步），此时到达 null，累计 a + c 步；
跳接到 B 的头节点，再走完 B 的非公共前缀（b 步），到达公共结点 c1，累计 a + c + b 步。

同理，l2 从 B 头出发，先走 b + c 步到 null，再跳去 A 走 a 步，也在累计 b + c + a 步时到达 c1。

由恒等式 a + c + b = b + c + a，两指针走过的总步数完全相同，且路径的终点都是同一个公共结点 c1——因此它们必定同时、同点到达交点，l1 == l2 成立，循环退出，l1 即第一个公共结点。

可以举个具体例子验证：设 a = 2、b = 3、c = 3（对应图中 a1、a2 与 b1、b2、b3，公共段 c1、c2、c3）。l1 的路径是 A 全长 5 步 → 跳 B → 再走 3 步到 c1，共 8 步；l2 是 B 全长 6 步 → 跳 A → 再走 2 步到 c1，共 8 步。同步到达，验证通过。

边界情形分析

这段代码的巧妙之处在于，所有边界情形都不需要额外分支：

情形	行为
两链表相交（常规）	如上推导，`a+b+c` 步后同时到达交点
两链表不相交（`c = 0`）	`l1` 走 `a + b` 步后为 null，`l2` 走 `b + a` 步后也为 null；步数相同，两指针同时变为 null，`l1 == l2 == null` 使循环退出，返回 null，语义正确
其中一个入参为 null	例如 `pHead1 = null`，`l1` 首轮即跳到 `pHead2`，之后两指针沿同一条链表同步前进，最终同时为 null，返回 null
两指针入参相同（`pHead1 == pHead2`，甚至同一对象）	`while (l1 != l2)` 初始即为假，直接返回头节点，正确

特别要理解"不相交"场景的终止性：由于两指针每一步的推进规则完全对称，步数严格同步，不存在一方先到 null、另一方还在走的"追不上"问题，因此算法不会死循环。

复杂度分析

时间复杂度：O(a + b)。两指针各自最多走 a + b + c 步（有交点）或 a + b 步（无交点），是线性时间的下界量级；
空间复杂度：O(1)。除两个指针变量外没有使用任何辅助结构。

解法对比：哈希集与长度对齐

双指针法是最优解，但面试中常要求给出其他可行方案作对照，便于说明取舍。

方案一：哈希集。先遍历链表 A，把所有结点存入 HashSet；再遍历链表 B，第一个出现在集合中的结点即公共结点（因为 Y 型结构中公共结点必然连续位于尾部，首次命中的一定是"第一个"）。时间 O(a + b)，空间 O(a)。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    Set<ListNode> set = new HashSet<>();
    for (ListNode p = headA; p != null; p = p.next) {
        set.add(p);
    }
    for (ListNode q = headB; q != null; q = q.next) {
        if (set.contains(q)) {
            return q;
        }
    }
    return null;
}

方案二：长度对齐。分别遍历两链表得到长度，让较长链表的指针先走长度差步，再让两指针同步前进，首次相遇点即交点。时间 O(a + b)（需遍历两遍量），空间 O(1)。它思路直观，但需要先跑两趟统计长度，代码行数比双指针法多，且对"不相交"必须显式处理（对齐后走完仍无相遇则返回 null）。

相比之下，双指针法用一个恒等式把"长度差"问题消解掉，不需要统计长度、不需要额外容器，是时间与空间都最优、且代码最紧凑的方案，这也是它成为标准答案的原因。

常见追问与易错点

1. 为什么判断条件是"同一结点"而不是"相同值"？ 链表值可能重复，但结点对象（引用地址）唯一。公共结点的定义是引用同一对象，比较 l1 != l2 用的是引用相等，这保证了即使公共段上出现相同的 val 也不会误判。

2. 如果链表带环怎么办？ 双指针法的前提是两链表均为无环单链表。若不确定是否带环，需要先做环检测：这正是仓库中23. 链表中环的入口结点讲的 Floyd 快慢指针法（快指针每次走两步、慢指针每次走一步，相遇则有环）。两链表各自无环且共享尾部时，"第一个公共结点"问题才成立；若公共段本身成环，问题形态完全改变，需另作分析。

3. 为什么循环体内要先判空再取 next？ 原实现中 l1 = (l1 == null) ? pHead2 : l1.next 的写法把"到头换链"与"正常前进"合并成一条三元表达式，避免了对 null.next 的解引用，是这一算法的标准写法，手写时不要拆错顺序。

4. 交点为什么必然在尾部（Y 型而非 X 型）？ 单链表中每个结点的后继唯一。若两链表在某结点相交，从该结点向后走的路径只有一条，故不可能出现分叉再交叉的结构。这一结构特征是上述长度恒等式成立的前提，也是面试中值得主动说明的一点。