相交链表

问题拆解

两条单链表可能在某个节点开始合并（之后完全共享同一段尾巴），要找出这个起始交点，没有则返回 null。

难点在于两条链表长度不一样，headA 和 headB 到交点的距离不同，直接齐头并进不会同时到达交点。如果先算出两边长度差，让长的那条先走几步再一起走，也能做，但要多遍历一遍算长度。

有一个更巧的对齐方式：让指针 A 走完链表 A 再接着走链表 B，指针 B 走完链表 B 再走链表 A。两者走过的总长度都是 lenA + lenB，于是会在同一时刻到达交点。

双指针换轨

def getIntersectionNode(headA, headB):
    pa, pb = headA, headB
    while pa is not pb:
        pa = pa.next if pa else headB
        pb = pb.next if pb else headA
    return pa

设两条链表非公共部分长 a、b，公共部分长 c。指针 A 到交点走 a + c + b 后到达，指针 B 走 b + c + a 后到达，两者相等，所以必定在交点相遇。

如果不相交，c = 0，两个指针会在各自走完 a + b 后同时变成 None，此时 pa is pb 成立（都是 None），循环退出返回 None。这个分支正好被同一段代码覆盖，不用特判。

复杂度

指标	复杂度	原因
时间	O(m + n)	每个指针最多走两条链表的总长
空间	O(1)	只用两个指针

可以迁移的模式

• 两个长度不等的序列要对齐时，“各走一遍再换到对方”能凑出相同的总路程；
• 用 is 判断是不是同一个节点，而不是比较值；
• 把“不相交”设计成“同时到达 None”，就能和相交情形共用一套循环。

换轨这招的核心是构造一个两边相等的总长度，让不同步的起点自然对齐。