LC160　相交链表¶

简单通过率 68.5%python3核心代码模式链表样例通过牛客 AC哈希表链表双指针

讲解章节：链表

一句话

两条单链表若在某个节点后合成一条，返回那个相交的起始节点，否则返回 null。

解题思路¶

这题考什么¶

相交的定义是节点同一个对象，不是值相等。两条链一旦相交，从相交点起后面的部分完全共享，所以两条链的尾部长度相同、只有前缀长度不同。设公共尾部长 c，链 A 的独有前缀长 a，链 B 的独有前缀长 b，则 A 长 a + c、B 长 b + c。两个指针各从自己的表头出发，一旦步数不同就永远对不齐——问题就出在 a 与 b 不相等。

换轨技巧把这个差抹平：指针 pa 走完 A 之后接着从 B 的表头继续走， pb 走完 B 之后从 A 的表头继续走。中间会各在 None 上停一步（下面的代码正是靠这一步统一处理无交点的情况），于是第二轮到达相交点时

pa 共走了 (a + c + 1) + b 步，pb 共走了 (b + c + 1) + a 步

两者相等，于是它们同时落在相交点上，一次身份比较就能抓到。直观说法是「你走过我走过的路，我走过你走过的路，我们就会在岔口相遇」。

没有交点时同一套代码也对：此时 c = 0，pa 与 pb 各走 m + n + 1 步后同时变成 None（各自踏空一次、换轨一次、再走完对方整条链），循环条件 pa is not pb 在两个 None 上不成立，自然退出并返回 None，不需要任何额外判断。链表基础见链表。

数据规模与复杂度¶

两条链的长度 m、n 都在 1..3 * 10^4，val 取 1..10^5。每个指针最多走 m + n + 1 步，时间 O(m + n)，约 6 * 10^4 步；额外空间只有两个指针，O(1)，正是进阶要求的组合。

哈希集合做法（先把 A 的全部节点丢进 set，再遍历 B 查第一个命中的）时间同样 O(m + n)，但要存下最多 3 * 10^4 个节点引用，空间 O(m)。先量两条链长度、让长的先走差值步再同步前进，空间也是 O(1)，但要多遍历两遍量长度，代码反而更长。

坑在哪¶

判断相交只能用 is 比身份，绝不能比 val。题面的相交定义是同一个节点对象，两条不相交的链完全可能含有相同的值（样例三的 [2,6,4] 与 [1,5] 换成含相同值的数据就会误判）；
换轨时接的是对方的表头，不是自己的表头。接自己的表头等于两个指针各自在自己的链上打转，长度差永远抹不平，无交点时还会变成死循环；
换轨的判断要写成「当前指针为 None 就跳到对方表头」，而不是「走到尾节点就跳」。少走那一步会让两个指针的总步数各差 1，无交点时错开，两个 None 不同时出现，循环停不下来；
每个指针只换一次轨，循环必定在 m + n + 1 步内结束——有交点时在交点相遇，无交点时同时踏空成 None。不必额外设步数上限；
题面附带的 intersectVal、skipA、skipB 只是评测系统用来搭出相交结构的描述，函数拿不到它们，也不该去用；真正的输入只有两个表头。

样例复核¶

示例二：A = [1,9,1,2,4]、B = [3,2,4]，从值 2 的节点起相交，故 a = 3（A 独有的 1、9、1）、b = 1（B 独有的 3）、c = 2（公共的 2、4）。 pa 依次经过 A0..A4、None、B0，第 7 步落到 B1； pb 依次经过 B0..B2、None、A0、A1、A2，第 7 步落到 A3。 B1 与 A3 是同一个对象（值 2 的那个节点），返回它，与样例期望的 Intersected at '2' 一致。

参考实现¶

solutions/leetcode/LC160/sol.py
from typing import List, Optional


class Solution:
    def getIntersectionNode(self, headA: "Optional[ListNode]", headB: "Optional[ListNode]") -> "Optional[ListNode]":
        # 两个指针各从自己的表头出发；走完自己的链就换到对方的链头继续
        pa = headA
        pb = headB
        # 用 is 比身份：相交的定义是同一个节点对象，值相同不算相交。
        # 无交点时两者会同时变成 None，这个条件同样能让循环停下来
        while pa is not pb:
            # 判空再换轨，而不是「到尾节点就换」：少走这一步会让两边总步数差 1，
            # 无交点时两个 None 不同时出现，循环就再也退不出去
            pa = pa.next if pa else headB
            pb = pb.next if pb else headA
        # 有交点时 pa 停在交点，无交点时 pa 是 None，两种情况都直接返回
        return pa

LC160 相交链表¶