#160
简单
高频
双指针相交链表
这是一道围绕链表、图展开的高频练习。建议先掌握「双指针」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
链表
图
题目分析
这道题表面上是在处理「相交链表」，但先要想清楚题目到底让你返回什么，以及过程中哪些约束必须一直满足。从题型上看，它主要在考 链表、图 这些能力。这类题通常依赖两个位置之间的相对移动，关键是先明确每次移动的依据是什么。只有先把题目要求翻译成人话，后面的推荐代码才是在实现思路，而不是直接给答案。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：两个指针分别走完自己的链表后切到对方头部，第二轮会在交点或 null 处对齐相遇。
推荐代码
推荐解法：双指针
时间复杂度： O(m+n)
空间复杂度： O(1)
核心思路： 两个指针分别走完自己的链表后切到对方头部，第二轮会在交点或 null 处对齐相遇。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode pA = headA, pB = headB;
while (pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
}
结构化讲解
面试时怎么讲
开场思路
这题我会用双指针切换链表头，让它们自动对齐路程。
核心过程
- 两个指针分别从两条链表头部出发。
- 走到尾部后，就切到对方链表继续走。
- 这样两个指针最终都会走完
A+B的总长度。 - 因此如果存在交点，它们会在交点相遇；否则一起到 null。
复杂度总结
时间复杂度 O(m+n)，空间复杂度 O(1)。
面试补一句：这题最值钱的解释是“让两指针走相同总长度”。
核心思路
相交链表的关键不是比较值，而是让两个指针走过同样总长度。切换头节点后，它们都会走完 A+B，因此自然对齐。
步骤讲解
1
两个指针从两条链表头部出发
分别让 pA 指向 A 链表头，pB 指向 B 链表头。
为什么这样做：后续它们会靠切换头节点来消除长度差。
对应代码提示：ListNode pA = headA, pB = headB;
2
走到尾部后切到对方链表
当某个指针走到 null，就让它从另一条链表头重新开始。
为什么这样做：这样两个指针最终都走过相同总长度。
对应代码提示：pA = (pA == null) ? headB : pA.next;
3
相遇点就是交点
如果两链表相交，两个指针会在交点相遇；若不相交，则最终一起为 null。
为什么这样做：总路程对齐后，它们只可能在真实交点或终点 null 处相遇。
对应代码提示：while (pA != pB) { ... }
易错点
比较节点值而不是节点引用
相交定义是“同一个节点对象”，不是值相等。
正确理解：必须比较节点引用是否相同。
没理解为什么能对齐
如果说不清两轮总长度相同，面试里很容易被追问卡住。
正确理解：明确说明两指针最终都走了
A+B 长度。一边切头，另一边不切
长度差无法消除，算法就失去成立前提。
正确理解：两边都要在走到 null 时切到对方头部。
复杂度与适用判断
时间复杂度：O(m+n)
空间复杂度：O(1)
比其他方案更好在哪里：比哈希表判重更省空间，是这题最经典的最优解。
适用判断：链表题需要消除长度差时，优先考虑双指针换头对齐。
额外提醒
- 相交看的是节点引用相同，不是节点值相同。
其他语言 / 其他解法
哈希表优化
哈希表法：
- 遍历链表A，将每个节点存入哈希表
- 遍历链表B，检查每个节点是否在哈希表中
- 第一个在哈希表中出现的节点即为相交节点
时间复杂度：O(m + n)，其中m和n分别为两个链表的长度
空间复杂度：O(m)，需要额外的哈希表存储链表A的所有节点
哈希表优化
哈希表法：
时间复杂度：O(m + n)，其中m和n分别为两个链表的长度
空间复杂度：O(m)，需要额外的哈希表存储链表A的所有节点
时间复杂度：O(m + n)
空间复杂度：O(m)
一句话思路：哈希表法：
- 遍历链表A，将每个节点存入哈希表
- 遍历链表B，检查每个节点是否在哈希表中
- 第一个在哈希表中出现的节点即为相交节点
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Set<ListNode> visited = new HashSet<ListNode>();
ListNode temp = headA;
while (temp != null) {
visited.add(temp);
temp = temp.next;
}
temp = headB;
while (temp != null) {
if (visited.contains(temp)) {
return temp;
}
temp = temp.next;
}
return null;
}
}
动画演示
如果你还没完全看懂，可以展开动画演示。
双指针动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
双指针动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪 - 输入两个链表的值和相交点位置，然后点击开始
哈希表优化动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
哈希表优化动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪 - 输入两个链表的值和相交点位置，然后点击开始
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。