Intersection of Two Linked Lists
Find the node where two linked lists merge in O(1) space: two pointers that each walk one list then the other meet at the intersection or at NULL.
Problem Understanding
Intersection of Two Linked Lists: given the heads of two singly linked lists, return the node at which they merge, meaning the first node shared by both. Return null if they never meet. The lists have no cycles and must not be modified.
Example: A = [4, 1, 8, 4, 5], B = [5, 6, 1, 8, 4, 5], sharing the tail from 8: return the node 8.
The Intuition: Walk Both Lists
The trouble is that the two lists can be different lengths before the shared part, so pointers that start together reach the tail at different times. The fix is to make both pointers walk the same total distance:
- Pointer
awalks A, then jumps to the head of B. - Pointer
bwalks B, then jumps to the head of A. - Each covers
lenA + lenBnodes, so after the jump they are lined up with the end.
They meet at the first shared node, or both at NULL if there is none. Like Linked List Cycle and Middle of the Linked List, it is a two-pointer linked list trick that avoids extra memory.
Interactive Walkthrough
a AT HEAD A, b AT HEAD B
list A
a
→
→
→
→
→
NULL
list B
b
→
→
→
→
→
→
NULL
a on A
4
b on B
5
Answer
—
a starts at the head of A (4), b at the head of B (5)
Next
a → 1; b → 6
A: prefix | tail
B prefix
Legend & Complexity
Pointer a
Pointer b
The shared tail (the same nodes in both lists)
Time
O(m + n)
Space
O(1)
Both lists are drawn in full; the shared tail is tinted in both rows because it is the same nodes. Each pointer appears on the row of the list it is walking, so you can see it jump to the other list's head. Enter list A as prefix | tail. Try Example 3 to see both reach NULL together.
Dry Run Table
Input: A = 4 → 1 → [8 → 4 → 5], B = 5 → 6 → 1 → [8 → 4 → 5]
| Step | a | b |
|---|---|---|
| 0 | 4 (A) | 5 (B) |
| 1 | 1 | 6 |
| 2 | 8 | 1 |
| 3 | 4 | 8 |
| 4 | 5 | 4 |
| 5 | NULL | 5 |
| 6 | 5 (B head) | NULL |
| 7 | 6 | 4 (A head) |
| 8 | 1 | 1 |
| 9 | 8 | 8 |
They meet at the shared node 8.
The Solution Template
Two pointers that switch to the other head when they fall off the end. Compare nodes, not values.
Intersection of Two Linked Lists Code
1var getIntersectionNode = function(headA, headB) {2 let a = headA, b = headB;3 while (a !== b) {4 a = a ? a.next : headB;5 b = b ? b.next : headA;6 }7 return a;8};
Edge Cases & Common Mistakes
- No intersection: both pointers reach NULL on the same step, and NULL is returned; the loop cannot run forever.
- Comparing values: equal values are not an intersection; compare node references.
- Switching to the wrong head: a must jump to headB and b to headA, or the distances do not line up.
- Same length lists: the pointers meet on the first pass without switching.
- Hash set approach: storing A's nodes works in O(m) space; the two-pointer version needs O(1).
Summary
Start a at headA and b at headB. Advance both, sending each to the other list's head when it falls off the end. Both travel lenA + lenB nodes, so they meet at the first shared node or at NULL together. O(m + n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet