LeetCode 160. 相交链表
题目描述
题意分析
给定两条无环单链表，返回它们的第一个公共节点；如果没有公共节点，返回空。这里的相交指两条链引用了同一个节点对象，节点值相同并不代表相交。
单链表的节点只有一个后继，因此一旦两条链走到同一个节点，之后的整段后缀都会相同，不会再分开。要求找到共享后缀的入口，并保持两条链表的原有结构。
解法：双指针交替遍历
核心思路
[!blue]
如果两条链等长，从各自头节点同时前进，就会同时到达第一个公共节点。一般情况下，两条链在交点之前的长度不同，直接同步前进可能错过彼此，因此要先消除这段长度差。
不必实际计算长度：令
p先走 A 再走 B，令q先走 B 再走 A。两者都走过对方的独立前缀后，额外路程就相互抵消了。设 A、B 在相交前的独立前缀长度分别为
a、b，公共后缀长度为c。交换链表后，到达公共入口之前，p经过a + c + b个节点，q经过b + c + a个节点；两者还各经历一次从空节点切换到另一链头的更新。总路程相同，所以会同步到达公共入口。若本来就已经对齐，则会在第一次遍历时提前相遇。如果不相交，两者走完 A、B 两条链的总长度同样相等，最终会同时成为空指针。因此用
p != q作为循环条件，既能在交点结束，也能在无交点时结束，不需要额外标记或修改链表。
解题步骤
- 初始化
p = headA、q = headB。- 当两个指针不是同一个节点时，分别更新一次它们的位置。
- 若
p非空，就前进到p.next；若已经为空，就切换到headB。- 对
q做对称处理：非空时前进，为空时切换到headA。- 两者相同时返回
p。它可能是共享后缀的入口，也可能是表示不相交的空指针。
代码实现
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p = headA;
ListNode q = headB;
// 相同节点或同时为空都会结束，比较的是对象身份。
while (p != q) {
// 走到空后转向另一条链，抵消两条前缀的长度差。
p = p == null ? headB : p.next;
q = q == null ? headA : q.next;
}
return p;
}
}
func getIntersectionNode(headA *ListNode, headB *ListNode) *ListNode {
p, q := headA, headB
// 相同节点或同时为空都会结束，比较的是对象身份。
for p != q {
// 走到空后转向另一条链，抵消两条前缀的长度差。
if p == nil {
p = headB
} else {
p = p.Next
}
if q == nil {
q = headA
} else {
q = q.Next
}
}
return p
}
复杂度分析
设两条链表的长度分别为
m、n。
- 时间复杂度：$O(m+n)$，每个指针最多遍历两条链各一次，加上常数次切换就会结束。
- 空间复杂度：$O(1)$，只使用两个指针，不记录节点集合。
关键点总结
[!green]
- 相交意味着共享后缀，所以问题的关键是消除入口之前的长度差。
- 两指针交换遍历顺序，使它们在相遇前走过相同长度的路程。
- 两个空指针也相等，因此同一个终止条件覆盖有交点和无交点。
易错点总结
[!yellow]
- 比较节点值会把两个独立但数值相同的节点误判为相交，必须比较节点引用。
- 应先允许指针到达空节点，再在下一轮切换链头；若在尾节点直接切换，无交点时可能永远循环。
- 循环条件若额外要求两个指针都非空，就会在第一次走完较短链时提前退出，来不及消除长度差。
- 本题保证链表无环。不能把这套“走到空节点再切换”的方法直接用于带环链表。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 补充题 119. 链表相交判定（允许有环） | 中等 | 本题两链表无环，切换链头可消除长度差；允许带环后还需区分入环点与同环情形。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！