LeetCode 160: Intersection of Two Linked Lists (Two Pointers, Head Switch)
LeetCode 160Linked ListTwo PointersToday we solve LeetCode 160 - Intersection of Two Linked Lists.
Source: https://leetcode.com/problems/intersection-of-two-linked-lists/
English
Problem Summary
Given heads headA and headB, return the first shared node if the two singly linked lists intersect; otherwise return null. Node identity (reference), not value equality, defines intersection.
Key Insight
If pointer A traverses A then B, and pointer B traverses B then A, both pointers walk the same total distance lenA + lenB. Therefore they either meet at the intersection node or both end at null.
Brute Force and Limitations
Baseline approach: compute lengths, align starts by advancing the longer list by |lenA-lenB|, then move together. It is correct and still O(n), but requires extra length pass and offset logic.
Optimal Algorithm Steps (Two Pointers with Head Switch)
1) Initialize pA = headA, pB = headB.
2) While pA != pB, move each pointer one step.
3) When pA reaches null, redirect it to headB; similarly redirect pB to headA.
4) Loop exits when pointers meet at intersection or both are null.
Complexity Analysis
Time: O(lenA + lenB).
Space: O(1).
Common Pitfalls
- Comparing node values instead of node references.
- Forgetting head switch, which breaks distance equalization.
- Attempting to modify list structure (not required).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode pA = headA;
ListNode pB = headB;
while (pA != pB) {
pA = (pA == null) ? headB : pA.next;
pB = (pB == null) ? headA : pB.next;
}
return pA;
}
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func getIntersectionNode(headA, headB *ListNode) *ListNode {
pA, pB := headA, headB
for pA != pB {
if pA == nil {
pA = headB
} else {
pA = pA.Next
}
if pB == nil {
pB = headA
} else {
pB = pB.Next
}
}
return pA
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* pA = headA;
ListNode* pB = headB;
while (pA != pB) {
pA = (pA == nullptr) ? headB : pA->next;
pB = (pB == nullptr) ? headA : pB->next;
}
return pA;
}
};# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
pA, pB = headA, headB
while pA is not pB:
pA = headB if pA is None else pA.next
pB = headA if pB is None else pB.next
return pA/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
var getIntersectionNode = function(headA, headB) {
let pA = headA;
let pB = headB;
while (pA !== pB) {
pA = (pA === null) ? headB : pA.next;
pB = (pB === null) ? headA : pB.next;
}
return pA;
};中文
题目概述
给定两个单链表头节点 headA 和 headB，若两链表相交，返回第一个公共节点；否则返回 null。注意相交依据是“节点引用相同”，不是值相同。
核心思路
让指针 A 走完 A 链后切到 B 链，指针 B 走完 B 链后切到 A 链。两者总路程都变成 lenA + lenB，因此会在交点相遇；若无交点，则会同时走到 null。
基线解法与不足
基线可先分别求长度，再让长链先走 |lenA-lenB| 步，随后双指针齐步走。思路正确但实现更繁琐，需要额外长度遍历与对齐逻辑。
最优算法步骤（双指针换头）
1）初始化 pA=headA、pB=headB。
2）当 pA != pB 时持续前进。
3）某指针到 null 后切到另一条链表头。
4）最终要么在交点相遇，要么同时为 null。
复杂度分析
时间复杂度：O(lenA + lenB)。
空间复杂度：O(1)。
常见陷阱
- 把“值相等”误当作“节点相同”。
- 忘记换头，导致无法抵消长度差。
- 试图修改链表结构，违背题意且没必要。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode pA = headA;
ListNode pB = headB;
while (pA != pB) {
pA = (pA == null) ? headB : pA.next;
pB = (pB == null) ? headA : pB.next;
}
return pA;
}
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func getIntersectionNode(headA, headB *ListNode) *ListNode {
pA, pB := headA, headB
for pA != pB {
if pA == nil {
pA = headB
} else {
pA = pA.Next
}
if pB == nil {
pB = headA
} else {
pB = pB.Next
}
}
return pA
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* pA = headA;
ListNode* pB = headB;
while (pA != pB) {
pA = (pA == nullptr) ? headB : pA->next;
pB = (pB == nullptr) ? headA : pB->next;
}
return pA;
}
};# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
pA, pB = headA, headB
while pA is not pB:
pA = headB if pA is None else pA.next
pB = headA if pB is None else pB.next
return pA/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
var getIntersectionNode = function(headA, headB) {
let pA = headA;
let pB = headB;
while (pA !== pB) {
pA = (pA === null) ? headB : pA.next;
pB = (pB === null) ? headA : pB.next;
}
return pA;
};
Comments