相交链表 · 双指针切换对齐长度

返回节点引用

A: 4→1→8→4→5,B: 5→6→1→8→4→5,在节点 8 相交(a=2,b=3,c=3)

长度分段

a = 2 (A 独有) · b = 3 (B 独有) · c = 3 (公共尾巴)

返回值

node(val=8)

双指针切换O(m+n) 时间O(1) 空间

判断的是节点引用是否相同,不是 val 是否相同。

当前结果: node(8)

1/11 · 题目与输入

当前发生了什么

A: 4→1→8→4→5,B: 5→6→1→8→4→5,在节点 8 相交(a=2,b=3,c=3)

机器状态：headA = a0, headB = b0

为什么正确：返回的是相交节点引用,不是节点值;比较时必须写 pA == pB,不能比较 Val。

不变量：相交意味着两条链从某个节点开始共享同一段后缀。

A 独有段B 独有段公共尾巴 pA pB 交点

状态面板

step: 0
pA: nil
pB: nil
pA 已切换: 否
pB 已切换: 否
pA == pB: 否

Go 代码

1func getIntersectionNode(headA, headB *ListNode) *ListNode {
2    pA, pB := headA, headB
3 
4    for pA != pB {
5        if pA == nil {
6            pA = headB
7        } else {
8            pA = pA.Next
9        }
10 
11        if pB == nil {
12            pB = headA
13        } else {
14            pB = pB.Next
15        }
16    }
17 
18    return pA
19}

面试回答区

两个指针分别从 headA、headB 出发;各自走完一条链就切换到另一条链头, 相当于 pA 走 A+B、pB 走 B+A。
设 A 独有长 a=2,B 独有 b=3,公共尾巴 c=3,两者总路程都是 a+b+c=8,会在第一个公共节点相遇(本例 val=8)。
比较的是节点引用 pA == pB,不是比较 Val。
时间复杂度 O(m+n),额外空间 O(1),不需要哈希表或预处理长度。