BM10　两个链表的第一个公共结点¶

简单通过率 37.42%python3核心代码模式样例通过牛客 AC链表

讲解章节：链表

一句话

两个指针走完自己再走对方，路程相等必在交点相遇。

解题思路¶

这题考什么¶

单链表每个节点只有一个 next，所以两条链一旦相交，后面就完全重合，整体形状是个「Y」而不是「X」。难点在于两条前缀长度不同，同步走会错位。

经典技巧「走对方的路」：p1 走完链 1 就跳到链 2 的表头，p2 走完链 2 跳到链 1 的表头。设两条前缀长度分别为 a、b，公共段长 c，那么两个指针到达交点时走过的总路程都是 a + b + c + 1（末尾的 None 也占一步），步数相同，所以必然同时踏上第一个公共节点。

没有公共节点时，两者同时走满 a + b + 2 步（各自末尾的 None 也算一步）后一起变成 None，p1 is p2 成立，循环退出返回 None，不需要额外判断，这是这个写法最漂亮的地方。链表结构见链表。

数据规模与复杂度¶

n <= 1000，其他语言时限 2 秒、空间限制 128M（比本系列其他题的 512M 紧）。每个指针最多走 a + b + c + 1 步，时间 O(n + m)、额外空间 O(1)，满足题面要求。哈希表法（先把链 1 的节点全放进 set，再拿链 2 逐个查）思路更直白，但要存下最多 1000 个节点引用，是 O(n) 空间，用不上「相交后完全重合」这个结构性质。

坑在哪¶

本题的输入是三段：{1,2,3},{4,5},{6,7}——链 1 独有的部分、链 2 独有的部分、两者共用的部分。后台把第三段拼成 Y 型的公共尾巴，两条链共享同一批节点对象，不是各造一份值相等的副本。函数签名里只有 pHead1 和 pHead2，看不出这回事；照第一二段建两条独立的链去自测，公共段整个丢了，正例必挂。本仓库的复现见 driver.py；
承接上一条，比较必须用 is（同一个对象）而不是 ==（值相等）。题面没有保证节点值互异，值相同的两个不同节点不是公共结点；
跳转条件写成 p1.next if p1 else pHead2，用 None 本身当跳转信号，也就是「走到尽头的下一站是对方的表头」。若改成「p1.next 为 None 就跳到对方头」，两个指针永远碰不到 None，无交点时会一直转圈死循环；
p1 跳的是 pHead2、p2 跳的是 pHead1，跳错方向就变成各自在原链上打转，路程不再相等；
某条链为空时，p1 一开始就是 None，第一轮直接跳到对方表头，走完对方也没碰上，最终两者同为 None 退出，返回空，符合「没有公共节点返回空」。

样例复核¶

{1,2,3},{4,5},{6,7}：a = 3、b = 2、c = 2。 p1 依次经过 1,2,3,6,7,None,4,5,6，p2 依次经过 4,5,6,7,None,1,2,3,6，各走 a + b + c + 1 = 8 步后双双踏上节点 6，返回值为 6 的结点，与样例一致。

参考实现¶

solutions/nowcoder/BM10/sol.py
from typing import List, Optional


class Solution:
    def FindFirstCommonNode(self, pHead1: "Optional[ListNode]", pHead2: "Optional[ListNode]") -> "Optional[ListNode]":
        p1, p2 = pHead1, pHead2
        # is 而不是 ==：判题的公共段是同一批节点对象，要的是身份相同不是值相等
        while p1 is not p2:
            # 走到 None 时跳到对方链头，两边总路程都是 a+b+c+1，必然同步踏上交点；
            # 无交点时两者同一轮变成 None，条件不成立自然退出，无需特判
            p1 = p1.next if p1 else pHead2
            p2 = p2.next if p2 else pHead1
        return p1

BM10 两个链表的第一个公共结点¶