LeetCode 剑指 Offer 52. 两个链表的第一个公共节点
题目描述
题意分析
给定两条无环单链表，寻找它们开始共享的第一个节点，不相交时返回空节点。公共节点指的是同一个节点对象，不是两个值相等但分别创建的节点。
单链表的每个节点只有一个后继，所以一旦相交，此后的整段后缀都会共享。两条链表可以长度不同，也可能从头就共享；只需要返回节点，不应修改任何原有连接。
解法：双指针切换链表抵消长度差
核心思路
[!blue]
两个指针分别从两条链表的头出发，如果只同步前进，较长链表的指针还在独有前缀时，另一指针可能已经进入公共后缀。问题在于两条独有前缀长度不同，需要让两条路线补齐这段差距。
让指针走到空节点后，切换到另一条链表的头，并继续同步每次走一步。这样第一个指针走“先 A 后 B”，第二个走“先 B 后 A”，无需提前统计长度。
设 A、B 独有前缀的节点数分别为
a、b，公共后缀长度为c。若此前未相遇，第一个指针先走完 A，再走 B 的独有前缀，经历的节点数是a + c + b；第二个则是b + c + a。两者相同，而且各自都经历一次空指针换头，因此会同步到达公共后缀的第一个节点。如果两条链表不相交，两条组合路线仍都包含完整的 A 和 B，最终会同时走到空节点。用“两个指针是否相同”作为循环条件，就同时覆盖了在公共节点相遇和在空节点相遇两种结束情况。每次只移动局部指针，不改变链表结构。
解题步骤
- 令
first指向 A 的头，second指向 B 的头。- 两个指针不相同时继续循环，各自在一轮中移动一次。
- 指针非空时前进到后继，为空时改指向另一条链表的头。
- 指针相同时返回该指针：非空即首个公共节点，为空即没有交点。
代码实现
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode first = headA;
ListNode second = headB;
while (first != second) {
// 到空后换到另一条链，两条路线补齐彼此的长度差。
first = first == null ? headB : first.next;
second = second == null ? headA : second.next;
}
return first;
}
}
func getIntersectionNode(headA, headB *ListNode) *ListNode {
first, second := headA, headB
for first != second {
// 到空后换到另一条链，两条路线补齐彼此的长度差。
if first == nil {
first = headB
} else {
first = first.Next
}
if second == nil {
second = headA
} else {
second = second.Next
}
}
return first
}
复杂度分析
设两条链表的长度分别为 $m$、$n$。
- 时间复杂度：$O(m+n)$，每个指针至多走过两条链表并执行一次换头。
- 辅助空间复杂度：$O(1)$，只维护两个指针，原节点和连接均不改变。
关键点总结
[!green]
- 判断相交比较的是节点引用或指针，不是存储值。
- 换头使两条路线都补齐另一条链的长度，从而消除独有前缀长度差。
- 保留空节点作为可能的相遇位置，无交点时也能自然终止。
易错点总结
[!yellow]
- 比较节点值会把两条独立链表中的相同数值误判成公共节点。
- 走到空节点后再换头，不能在尾节点处直接跳过空节点；否则无交点时可能一直循环。
- 必须先判空，再访问后继，才能覆盖任一链表为空的情况。
- 两个指针每轮都只移动一次，推进速度不同会破坏路线补齐后的同步。
- 无需为了找交点临时连接或修改两条链表，也不能将该无环算法直接用于带环输入。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 补充题 119. 链表相交判定（允许有环） | 中等 | 本题两链表无环，切换链头可消除长度差；允许带环后还需区分入环点与同环情形。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！