8.9 KiB
tags, create time
| tags | create time | ||||
|---|---|---|---|---|---|
|
2026-05-16 14:30 |
22-相交链表
题面
给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 nil。
注意：
- 函数返回结果后，链表必须保持其原始结构。
- 整个链式结构中不存在环。
- 如果相交，相交节点的地址（引用）相同——仅值相等不算相交。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。在 A 中相交节点前有 2 个节点，在 B 中有 3 个节点。
示例 2：
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
示例 3（不相交）：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：No intersection
解释：两个链表不相交，因此返回 nil 。
提示：
listA中节点数目为m，listB中节点数目为n1 <= m, n <= 3 * 10^41 <= Node.val <= 10^5- 进阶： 你能否设计一个时间复杂度
O(m + n)、仅用O(1)内存的解决方案？
思路
[!question] 💡 关键区分 相交 ≠ 值相等。题目判断的是内存地址是否相同——即同一个节点对象被两个链表同时引用。值相同的不同节点不算相交。
[!info] 🧩 重要性质 由于每个节点最多只有一个
next指针，且不存在环，两个链表一旦相交就永远不会分开——它们从相交点开始形成 Y 字形共享尾部。这意味着：要么完全不相交，要么共享一段相同的后缀。
方法一：暴力枚举（O(m×n)）
对链表 A 的每个节点，遍历链表 B 的所有节点，检查是否存在地址相同的节点。
缺点： 时间复杂度太高，不满足进阶要求。直接跳过。
方法二：双指针交换法 ⭐（最优 O(m+n)，O(1) 空间）
[!question] 💡 引导思考 假设 A 长 m 个节点，B 长 n 个节点，两个指针 pA、pB 分别从 headA、headB 出发。如何让它们同时到达相交点？
核心洞察：让两个指针走等长的路程。
如果指针 pA 遍历完 A 后转到 B 头部继续走，指针 pB 遍历完 B 后转到 A 头部继续走——各自恰好走了 m + n 步。那么它们会在哪里相遇？
[!info] 🧮 关键等式：m + len(B→交点) = n + len(A→交点)
定义变量如下：
| 符号 | 含义 |
|---|---|
| pA, pB | 两个移动中的指针 |
| m, n | 链表 A、B 的总长度 |
| lenA | 从 headA 到交点的距离（即 skipA） |
| lenB | 从 headB 到交点的距离（即 skipB） |
| L | 共享后缀长度 = m − lenA = n − lenB |
指针 pA 的路径 = 「A 全长」+「B 中从开头走到交点」= m + lenB
指针 pB 的路径 = 「B 全长」+「A 中从开头走到交点」= n + lenA
两者相等吗？验证：
m + \text{lenB} = (\text{lenA} + L) + \text{lenB} = \text{lenA} + \text{lenB} + L
n + \text{lenA} = (\text{lenB} + L) + \text{lenA} = \text{lenA} + \text{lenB} + L
两边相等 ✅ — 都等于 lenA + lenB + L。
以示例 1（m=5, n=6, lenA=2, lenB=3, L=3）验证：
| 指针 | 路径拆解 | 总步数 |
|---|---|---|
| pA | 5（A 全长）+ 3（B 的前缀到交点） | 8 |
| pB | 6（B 全长）+ 2（A 的前缀到交点） | 8 |
两指针同步前进，总路程相等，必然在同一个位置首次相遇——那就是交点。
flowchart LR
subgraph A ["链表 A（4→1→[8→4→5]）"]
A1["4"] --> A2["1"]
A2 --> JC["8 ★ 相交点"]
JC --> JN1["4"]
JN1 --> JN2["5"]
JN2 --> NIL1["nil"]
end
subgraph B ["链表 B（5→6→1→[8→4→5]）"]
B1["5"] --> B2["6"]
B2 --> B3["1"]
B3 --> JC2["8 ★ 同一节点"]
JC2 -.-> JN1
JC2 -.-> JN2
JN2 --> NIL2["nil"]
end
style JC fill:#f9d,stroke:#333
style JC2 fill:#f9d,stroke:#333
图解两个指针的路径：
pA 的路径：headA → … → nil(A) → headB → … → JC ← 相遇！
pB 的路径：headB → … → nil(B) → headA → … → JC ← 同时到达！
| 时刻 | pA 所在位置 | pB 所在位置 | 说明 |
|---|---|---|---|
| 初始 | headA | headB | 各自主张的起点 |
| 第 2 步 | A 中第 2 个 | B 中第 3 个 | 各自在自己的链表中 |
| 第 5 步 | nil（A 末尾） | nil（B 末尾） | 各自走完自己的链表 |
| 切换 | headB[1] | headA[1] | null 时切换到对方头部 |
| 第 8 步 | JC | JC | 同时到达相交点！ |
[!warning] ⚠️ 如果不相交呢？ 如果没有相交点，两个指针会继续走完
m + n步后都停在nil。此时 pA == nil && pB == nil，退出循环，返回 nil。逻辑仍然正确。
时间复杂度：O(m + n) — 每个指针最多遍历两条链表的总长度。 空间复杂度：O(1) — 只使用两个指针变量。
[!note] 🤔 为什么一定在相交点相遇而不是更早或更晚？ 因为两指针同步前进（每步都移动），且走的总路程完全相等。第一个相遇的位置必然是第一次"踩到"同一个节点的时刻，也就是相交点。不可能更早相遇——否则那才是相交点；也不可能更晚——因为在相交点处路程已经对齐了。
代码提示
// 伪代码模板
pA := headA
pB := headB
for pA != pB {
if pA == nil {
pA = headB // pA 走完 A，转去走 B
} else {
pA = pA.next
}
if pB == nil {
pB = headA // pB 走完 B，转去走 A
} else {
pB = pB.next
}
}
return pA // pA == pB，要么是相交节点，要么是 nil
Go 语言技巧：
- Go 不支持多赋值同时推进两个指针到不同目标，需要用临时变量或逐行判断
- 利用 Go 的
nil语义：if node == nil安全且直观 - 也可以用
for循环内联两种切换逻辑，但拆分会更清晰易读
[!tip] 🔑 一行 Go 写法（竞赛向） 利用 Go 的短变量声明，可以在循环体内依次推进 a 和 b，利用延迟求值的特性完成切换：
```go
for pA != pB {
if pA == nil {
pA = headB
} else {
pA = pA.Next
}
if pB == nil {
pB = headA
} else {
pB = pB.Next
}
}
技巧
[!tip] 🔑 核心模式：交叉遍历（Cross Walk / Two-pointer Switching） 当两个序列长度不同但需要"对齐"时，让它们互相接管对方的剩余路程。本质是构造等长路径来消除长度差异。类似的变体包括「环形链表入口」（Floyd 判圈算法也用了对称思想）。
[!note] 🐹 Go 中的链表定义 LeetCode 的 Go 环境内置如下结构体定义：
type ListNode struct {
Val int
Next *ListNode
}
不需要手动定义，直接在解题中使用即可。
[!info] 📊 其他解法对比
| 方法 | 时间复杂度 | 空间复杂度 | 备注 |
|---|---|---|---|
| 暴力枚举 | O(m × n) | O(1) | 双重嵌套遍历，太慢 |
| 哈希集合 | O(m + n) | O(m) | 把 A 的所有节点存入 set，再遍历 B 查找 |
| 计算长度差 | O(m + n) | O(1) | 先求各自长度，长的先走差值步数 |
| 交叉遍历 ⭐ | O(m + n) | O(1) | 最优，无需预先遍历 |
[!success] ✅ 关于"计算长度差"法的补充 这也是 O(m + n) 和 O(1) 空间的合法方案，且更符合直觉：
- 分别遍历得到长度 lenA、lenB
- 让较长的链表先走 |lenA - lenB| 步
- 然后两个指针同步前进，第一个相同的节点就是相交点
缺点是需要两次遍历（一次算长度 + 一次找交点），而交叉遍历法虽然也遍历 m + n 步，但在实际运行中往往更快收敛到答案。
代码
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func getIntersectionNode(headA, headB *ListNode) *ListNode {
pA, pB := headA, headB
for pA != pB {
// pA 走完 A 后转到 B 头部
if pA == nil {
pA = headB
} else {
pA = pA.Next
}
// pB 走完 B 后转到 A 头部
if pB == nil {
pB = headA
} else {
pB = pB.Next
}
}
return pA // pA == pB，要么是非 nil 的相交节点，要么是 nil
}
[!success] ✅ 运行验证 这是 LeetCode 第 160 题，通过率约 50%。看似简单但双指针交换法非常优雅——它用"以空间换对称"的思想，将长度差异的问题转化为"一起绕一圈就能对齐"的自然过程。建议动手实现并理解其正确性证明（数学归纳：每一步 a 和 b 距离各自起点的步数之差恒等于 |m - n|）。