LeetCode 面试题 02.07. 链表相交
题目描述
题意分析
给定两条无环单链表，返回它们第一个共享的节点；不相交时返回空。相交表示两个引用指向同一个节点对象，而不是两个不同节点恰好具有相同的值。
单链表每个节点只有一个后继，因此一旦相交，后面的整段链表都会共享。两条链各自的独有前缀长度可能不同，直接从两个头同步前进，未必能同时到达交点；需要先消除这段长度差。
解法：双指针交换链表头
核心思路
[!blue]
两个指针分别从
headA、headB出发，每轮同步前进一步。某个指针走到空后，下一步转到另一条链表的头，形成先走 A 再走 B、先走 B 再走 A 的两条路线。整个过程只移动局部指针，不改动任何链表连接。设两条链独有前缀长度分别为
a、b，共享后缀长度为c。若第一轮没有提前相遇，换头后，A 指针走到共享入口所经过的节点路程是a + c + b，B 指针则是b + c + a；两边还各有一次从空切换到另一链头的操作，总步数仍相同。因此它们会同时到达第一个共享节点。两个独有前缀等长时，可能第一轮就相遇，不需要真的换头；两个头本来就相同也会直接返回。比较的是节点身份，所以不会在独有前缀中因为值相同而误判。
如果没有共享节点，两条路线都走完两条链表后，会同时到达空，循环同样结束并返回空。必须允许指针先走到空，再按同一规则换头；不能因为一侧先为空就提前判定不相交。
解题步骤
- 令两个指针分别指向
headA、headB。- 只要两个指针不是同一个节点，就各更新一步。
- 非空指针移动到后继，空指针切换到另一条链表的头。
- 两指针相等时返回任意一个；结果可能是共享节点，也可能是空。
代码实现
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA = headA;
ListNode curB = headB;
// 两个指针各走两条链表，总路程一致后自然消除长度差。
while (curA != curB) {
if (curA == null) {
// 走完一条后转到另一条，抵消两个独有前缀的长度差。
curA = headB;
} else {
curA = curA.next;
}
if (curB == null) {
curB = headA;
} else {
curB = curB.next;
}
}
return curA;
}
}
func getIntersectionNode(headA, headB *ListNode) *ListNode {
curA := headA
curB := headB
// 两个指针各走两条链表，总路程一致后自然消除长度差。
for curA != curB {
if curA == nil {
// 走完一条后转到另一条，抵消两个独有前缀的长度差。
curA = headB
} else {
curA = curA.Next
}
if curB == nil {
curB = headA
} else {
curB = curB.Next
}
}
return curA
}
复杂度分析
- 时间复杂度：$O(m+n+1)$，包含走到空后切换另一链头的操作。
- 空间复杂度：$O(1)$，不改变链表。
关键点总结
[!green]
- 相交后共享整个后缀，不是两条链中恰好出现相同数值。
- 允许先到空再切换，两边必须采用一致规则。
易错点总结
[!yellow]
- 按 val 判断相等会把不同节点误判成交点。
- 每次从头重新搜索另一个链表会增加不必要的重复遍历。
- 只同步从两头走一次，长度不同就可能错过交点。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 补充题 119. 链表相交判定（允许有环） | 中等 | 本题两链表无环，切换链头可消除长度差；允许带环后还需区分入环点与同环情形。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！