LeetCode 160. 相交链表
目录
题目描述
题意分析
输入两条单链表的头节点
headA和headB，要求返回它们的第一个公共节点；如果两条链表没有公共节点，返回空。「公共」指的是同一个节点对象被两条链表共用，而不是两个节点的值恰好相等。题目给出的示例里刻意安排了值重复的干扰节点，所以所有判断都必须比较节点身份，而不是
val。题目明确要求函数返回后两条链表必须保持原有结构，这一条排除了所有破坏性技巧：不能把一条链表反转、不能把尾节点接到另一条头上再复原之外的做法。同时题面说明链表中不存在环，因此不需要先做环检测。
结构上有一个决定性的事实：单链表每个节点只有一个
next。因此两条链表一旦共用了某个节点，从这个节点往后的所有节点必然也被共用。也就是说，相交的形态一定是「Y 型」——两段各自独立的前缀，接上一段完全重合的公共后缀，绝不可能相交之后又分开。需要单独考虑的边界：任意一条链表为空时答案必然是空；
headA == headB时整条链表都是公共部分，答案就是头节点；两条链表长度可以相差很大，甚至一条只有 1 个节点而另一条有上万个；两条链表尾部的值可能完全一样却互不相交，此时必须返回空。
解法：双指针交替遍历
核心思路
两条链表相交后会共享同一段后缀，难点只在于相交前的长度不同。指针
p走完链表 A 后改走 B，指针q走完 B 后改走 A；两者最终都走过A + B，会在交点相遇。若不相交，则同时变为null。
解题步骤
- 初始化
p = headA、q = headB。- 当
p != q时各前进一步。p到达空节点后切换到headB，q到达空节点后切换到headA。- 循环结束时返回
p；它是交点，或在不相交时为null。
代码实现
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
}
复杂度分析
- 时间复杂度：$O(m + n)$，两个指针最多各遍历两条链表一次。
- 空间复杂度：$O(1)$，只使用两个指针。
关键点总结
- 判断的是节点引用是否相同，不是节点值是否相等。
- 交换遍历顺序可以自动抵消两条链表的长度差。
p == q同时覆盖找到交点和两者均为空两种结果。
易错点总结
- 比较节点值会把值相同的独立节点误判为相交。
- 应在指针变为空后切换链表，而不是在尾节点处提前切换。
- 循环条件不要额外限制指针非空，否则可能提前退出。
- 找到相同节点后应直接返回该节点，不能返回其后继。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| LCR 023. 相交链表 | 简单 | 与本题同题，可用来分别默写双指针和哈希两版，检查边界是否都能一次通过 |
| 面试题 02.07. 链表相交 | 简单 | 同一模型的另一份题面，措辞更强调「按引用相交」，适合校对值相等的误区 |