Intersection of Two Linked Lists has an O(1)-space solution that looks like sleight
of hand: walk both lists, and whenever a pointer runs off the end, restart it at the other
list's head. They meet at the intersection. The trick is two lines; the reason it works is one
equation, and that equation is the answer.
The problem
Two singly linked lists may merge at some node and share every node from there on. Return the node where they intersect, or null. Intersection is by reference, not by value, and the lists must keep their original structure.
A: 4 -> 1 ↘
8 -> 4 -> 5 -> the node holding 8
B: 5 -> 6 -> 1 ↗
A: 2 -> 6 -> 4
B: 1 -> 5 -> null, no intersection
A: [3] B: [3] -> null (two SEPARATE nodes, equal values)That last case is the one to state back. Two distinct nodes both holding 3 do not intersect; comparing values instead of references reports an intersection that does not exist.
Why the obvious approaches are unsatisfying
| Approach | Time | Space |
|---|---|---|
| Hash set of A's nodes, scan B | O(m + n) | O(m) |
| Measure both lengths, advance the longer by the difference, walk together | O(m + n) | O(1) |
| Two pointers that swap lists | O(m + n) | O(1) |
The length-difference version is perfectly good and is the one most people arrive at. It needs three passes and a subtraction. The swap version does the same thing in one loop with no arithmetic, which is why it is worth knowing.
The equation
Write the lists as a shared tail of length c with private prefixes of length
a and b:
A: ---- a ----> [intersection] ---- c ----> null
B: -- b --> [intersection] ---- c ----> null
pointer starting on A, switching to B: a + c + b steps to the intersection
pointer starting on B, switching to A: b + c + a steps to the intersectiona + c + b = b + c + a. Both pointers arrive at the intersection after the same number
of steps, so they are there simultaneously. That is the whole proof, and it fits on one line — the
switch equalises the path lengths without ever measuring them.
If there is no intersection, c = 0 and both pointers reach null after
a + b steps. They become equal — both null — and the loop ends returning null. The
no-intersection case needs no special handling, which is the second nice property.
Switch on null, not on the last node
a = (a == null) ? headB : a.next; correct
a = (a.next == null) ? headB : a.next; WRONG -- skips a step, and loops forever
when the lists do not intersectThe pointer must actually become null before restarting, because null is the extra position that makes the two path lengths equal. Switching one node early makes them differ by one and the no-intersection case never terminates.
Java
class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode a = headA, b = headB;
// Both walk a + c + b steps, so they arrive together. If there is no
// intersection both become null at the same time and the loop ends.
while (a != b) {
a = (a == null) ? headB : a.next;
b = (b == null) ? headA : b.next;
}
return a;
}
}a != b is reference comparison. Using equals would report the
two-separate-3s case as an intersection.
Each pointer switches at most once, so the loop runs at most m + n + 1 times. Being
able to state that bound is what turns "it terminates" from a hope into a fact.
Python
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
if headA is None or headB is None:
return None
a, b = headA, headB
while a is not b: # `is not`, not `!=` -- identity
a = headB if a is None else a.next
b = headA if b is None else b.next
return ais not rather than !=, for the same reason as
Linked List Cycle: the question is
about object identity, and a value comparison would answer a different one.
Complexity
| Time | Space | |
|---|---|---|
| Swapping pointers | O(m + n) | O(1) |
Each pointer traverses each list at most once. No allocation, and neither list is modified — which the problem explicitly requires, and which rules out the tempting trick of marking visited nodes.
The follow-up worth anticipating
"What if the lists might contain cycles?" The algorithm breaks immediately — neither pointer ever reaches null, so the equalising step never happens.
The honest answer is that it becomes a different problem: detect a cycle in each with Floyd's algorithm from problem 141, then case-split on whether zero, one or both have one. Two cyclic lists intersect only if they share the same cycle, which you test by walking one cycle looking for the other's meeting point. Sketching the case split is enough; nobody expects the code.
The pattern
"Equalise two traversals by making each walk both paths" is the reusable idea, and it is rarer than it deserves to be. The same trick answers Lowest Common Ancestor (236) when nodes carry parent pointers: walk up from each node, switching to the other's start on reaching the root, and the two meet at the LCA for exactly the same reason.
The general shape: when two paths differ by an unknown offset, concatenating them in both orders makes the offsets cancel.
What the interviewer is checking
- That intersection means the same node, not the same value.
- That you can give the length-difference solution before the clever one.
a + c + b = b + c + a— the reason the swap works.- Switching on null, not on the last node.
- That no intersection terminates by itself, with both pointers null.
- Either list empty.
- That neither list is modified.