LeetCode LCR 023. 相交链表
题目描述
题意分析
给定两条无环单链表，返回它们第一个共享的节点；没有公共节点则返回空。共享指同一个节点对象，两个节点的值相等不能算相交。
单链表每个节点只有一个后继，所以一旦相交，后面的整段都会重合。两条链各自的前缀长度可以不同，目标是找到公共后缀的起点，并保持所有原连接不变。
解法：双指针换链抵消长度差
核心思路
[!blue]
若已知两条链的长度，可以让长链指针先走多出的部分，再同步前进。换链法实现相同的对齐效果，但不必显式计算长度差。
指针
a从 A 出发，走到空后切换到 B 的头；b从 B 出发，走到空后切换到 A 的头。设两条独占前缀分别有x、y个节点，公共后缀有z个节点。换链后到公共入口之前，
a先经过 A 的x+z个节点，再经过 B 的y个独占节点；b则先经过y+z个节点，再经过 A 的x个独占节点。两边合计都为x+y+z，且都经历一次“从空切到另一头”的更新，所以会在同一轮到达公共入口。若独占前缀等长，它们在第一次扫描时就已相遇。换链之前不同长度造成的错位，在每个指针补走另一条链的前缀后被抵消。公共入口之前都是独占节点，无法按引用相等，因此返回的就是第一个公共节点。
不相交时，每个指针最终都走过两条链，在至多
m+n+1次更新后同时为空。循环条件a != b同时覆盖“相交节点相同”和“都为空”两个出口。应等当前指针为空后再换链，保留这个能让无交点情况结束的状态。
解题步骤
- 初始化
a = headA、b = headB。- 当两个引用不相等时，分别更新它们。
- 当前指针非空就走向后继，为空就切到另一条链的头。
- 循环结束返回
a，它是公共入口或空指针。
代码实现
class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a = headA;
ListNode b = headB;
while (a != b) {
// 换链抵消长度差；没有交点时两个指针最终同时为空。
a = a == null ? headB : a.next;
b = b == null ? headA : b.next;
}
return a;
}
}
func getIntersectionNode(headA, headB *ListNode) *ListNode {
a, b := headA, headB
for a != b {
// 换链抵消长度差；没有交点时两个指针最终同时为空。
if a != nil {
a = a.Next
} else {
a = headB
}
if b != nil {
b = b.Next
} else {
b = headA
}
}
return a
}
复杂度分析
- 时间复杂度：$O(m+n)$，每个指针至多遍历两条链各一次，并进行一次链头切换。
- 空间复杂度：$O(1)$，只维护两个指针，原链表结构不变。
关键点总结
[!green]
- 相交后共享整条后缀，对齐进入后缀的时刻即可找到入口。
- 各自走完本链再接另一链，自动抵消独占前缀的长度差。
- 从空节点换链这一步在两侧相同，精确数更新次数时不能忽略。
- 引用相等既表示找到交点，也能表示不相交时双方都到空。
易错点总结
[!yellow]
- 比较节点值会把内容相同的不同节点误判为公共节点。
- 在尾节点直接跳转而不允许经过空状态，会使无交点时失去正常的终止出口。
- 不应为了拼接遍历路径而修改实际
next，换链只改变局部指针变量。- 两个头本来相同时直接返回，任一链为空也能由相同循环自然处理。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 补充题 119. 链表相交判定（允许有环） | 中等 | 本题两链表无环，切换链头可消除长度差；允许带环后还需区分入环点与同环情形。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！