LeetCode 剑指 Offer 52. 两个链表的第一个公共节点

约 5 分钟
文章信息 19 个分类 3 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 20-50 字节跳动 微软 美团 阿里巴巴 快手 腾讯 百度 滴滴 京东 商汤 虾皮 剑指 Offer 剑指 Offer（第 2 版）
标签
哈希表 双指针 链表
目录

题目描述

✅ 剑指 Offer 52. 两个链表的第一个公共节点

image-20241107211743246

题意分析

给两条单链表，若它们相交，返回相交处的第一个节点；不相交则返回 null。
这里的「相交」指的是两条链表从某个节点起共用同一批节点对象，而不是恰好有相同的值。所以判定标准是引用相等（Java 的 ==、Go 的指针比较），拿 val 去比会在存在重复值时给出错误答案。
从这个定义还能推出一个很有用的结构性质：单链表每个节点只有一个 next，一旦两条链在某点汇合，之后就再也分不开，因此相交部分一定是两条链共同的后缀，两条链的形状是「Y」而不是「X」。
约束里另有两点要留意：题目要求函数返回后链表结构保持原样，因此不能靠反转、断链或加环这类破坏性技巧；进阶要求 $O(1)$ 空间，直接排除了「把一条链的节点全塞进哈希集合」的做法。边界情形包括任一条链为空、两条链完全重合、以及交点就是某条链的头节点。

解法：双指针切换链表抵消长度差

核心思路

单链表一旦在某个节点相交，之后的后继都相同，因此答案是两条链的第一个公共后缀节点。直接同步前进的问题是两条链在交点前的长度可能不同；可以让两个指针走完自己的链后切换到另一条链，从而自动抵消长度差。

设 A、B 的独有前缀长度分别为 a、b，公共后缀长度为 c。指针 first 走过 A + B，到交点前的有效路程是 a + c + b；second 走过 B + A，对应路程是 b + c + a，两者相等。实现中两条路径还会经过相同的一次 null 边界，不影响等长结论。

状态不变量是：两个指针每轮各走一步，已走步数始终相同，并分别沿 A -> B、B -> A 两条等长路线前进。有交点时，它们会在第一个公共节点引用上相遇；无交点时，两者最终同时为 null，循环同样能结束。

解题步骤

  1. 令 first = headA、second = headB。
  2. 当两个指针引用不同时，各前进一步。
  3. 指针非空时走向 next；指针为空时切换到另一条链的头节点。
  4. 两个引用相同时退出：非空就是第一个公共节点，同时为空则表示不相交。

例如 A 为 4 -> 1 -> [8 -> 4 -> 5]，B 为 5 -> 6 -> 1 -> [8 -> 4 -> 5]。A 的指针先走完自己的较短前缀，换到 B 后补走较长前缀；B 的指针反向补齐同样的长度，最终同时到达同一个节点 8。注意判断的是节点对象，不是值。

代码实现

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode first = headA;
        ListNode second = headB;

        while (first != second) {
            first = first == null ? headB : first.next;
            second = second == null ? headA : second.next;
        }
        return first;
    }
}

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    first, second := headA, headB

    for first != second {
        if first == nil {
            first = headB
        } else {
            first = first.Next
        }
        if second == nil {
            second = headA
        } else {
            second = second.Next
        }
    }
    return first
}

复杂度分析

  • 时间复杂度：O(m + n)。两个指针至多各遍历两条链一次。
  • 空间复杂度：O(1)。只使用两个指针，不修改链表结构。

关键点总结

  • 公共节点的含义是引用相同；值相同的两个独立节点不算相交。
  • 换头并不是技巧记忆，其本质是让两条路线分别走 A + B 与 B + A，从而抵消前缀长度差。
  • 必须允许指针走到 null，这样无交点时也能在 null 相遇并终止。
  • 同一头节点、任一空链、等长或不等长链表，都由同一循环自然覆盖，无需特判。

易错点总结

  • 比较节点值：两条不相交链都含值 8，也不能返回其中任意一个 8，必须比较节点引用。
  • 在尾节点直接换头、跳过 null：无交点时可能在两条链之间永久错位，形成死循环。
  • 判空顺序错误：先访问 first.next 再判断 first == null，空链会立即触发空指针异常。
  • 两个指针推进速度不同：任一指针一轮多走一步都会破坏等长路线，可能越过交点。
  • 为求交点临时改链却不恢复：会污染输入结构；换头双指针完全不需要修改任何 next。

相似题目

题目 难度 考察点
141. 环形链表 简单 快慢指针判断是否有环，只需返回布尔值
142. 环形链表 II 中等 快慢指针相遇后再定位入环点，需要额外推导
160. 相交链表 简单 与本题完全同题，进阶明确要求 $O(1)$ 空间
287. 寻找重复数 中等 把数组视作隐式链表后套用环形链表的入环点推导
LCR 022. 环形链表 II 中等 入环点问题换编号，考察相遇点到入口的距离关系
LCR 023. 相交链表 简单 本题换编号，双指针换头写法可直接复用
剑指 Offer 22. 链表中倒数第k个节点 简单 同为双指针，但用固定间距而非换头来对齐位置