Intersection of Two Linked Lists
Return the node where two singly linked lists first intersect, or null if they never do.
- The number of nodes of listA is in the m.
- The number of nodes of listB is in the n.
- 1 <= m, n <= 3 * 10⁴
- 1 <= Node.val <= 10⁵
- 0 <= skipA <= m
- 0 <= skipB <= n
- intersectVal is 0 if listA and listB do not intersect.
- intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.
Intuition
Intersection of two linked lists finds the node where two lists merge, comparing by reference rather than value. Two nodes holding equal values are not an intersection; the lists must share the actual node.
Once they intersect, they share every node to the end, so the lists have a common tail of some length and differing prefixes. The difficulty is that the prefixes are usually unequal, so walking both from the head compares nodes at different distances from the end.
The elegant solution equalises the distances without measuring anything:
- Walk both lists, and on reaching the end of one, continue from the head of the other — both pointers then travel lenA + lenB and meet at the intersection.
The reason is that each pointer covers its own list plus the other's, so both travel the same total distance. After the switch they are equidistant from the end, and since the tails are shared, they arrive at the intersection together.
If the lists never intersect, both pointers reach null at the same step and the loop ends — that shared null is what makes the no-intersection case terminate rather than looping forever. Switching only when a pointer becomes null, and switching at most once each, is what guarantees it.
The explicit alternative measures both lengths, advances the longer list by the difference, then walks in step. Same O(n) cost, more code, and easier to reason about.
A hash set of visited nodes also works but uses O(n) space, which the two-pointer method avoids entirely.
Two pointers that switch lists on reaching the end both travel exactly lenA + lenB steps, so they arrive at the intersection together regardless of the original length difference. If there's no intersection they both hit None at the same moment, which the same loop condition catches for free.
Approach
Before reading on: price up what the direct approach costs here, then ask which pointers must be saved before you overwrite anything. Aim for O(m + n) time and O(1) space.
Compare references, not values
Two nodes with equal values are not an intersection. The lists must share the actual node object, which is what the equality test must check.
Note the shared tail
Once the lists meet they share every subsequent node. So they differ only in prefix length, which is what makes the distances unequal.
Switch heads at the end
Walk both lists, and on reaching null, continue from the other list's head. Each pointer then travels lenA + lenB in total.
Understand why they meet
Equal total distance means both pointers become equidistant from the end after switching. Since the tail is shared, they reach the intersection on the same step.
Let the null case terminate
With no intersection, both pointers reach null simultaneously and the loop ends. Switching only once each is what guarantees termination rather than an infinite loop.
Know the explicit alternative
Measure both lengths, advance the longer by the difference, then walk in step. Same O(m + n) cost with more code but simpler reasoning.
Cost of the approach
Each pointer traverses both lists once, giving O(m + n) time and O(1) space — the space advantage over a visited hash set.
Solution & live demo
Common pitfalls
Switching on a.next instead of a
a = a.next if a.next else headB
a = a.next if a else headB
Switching one node early means each pointer walks lenA + lenB - 1 steps, so they never align. The switch must happen after falling off the end, which is why the null value itself is the trigger.
Comparing values rather than identity
while a.val != b.val:
while a is not b:
The question asks where the lists share a node, not where they happen to hold equal numbers. Two distinct nodes with the same value would report a false intersection.
Guarding the loop against None
while a and b and a is not b:
while a is not b:
In the non-intersecting case both pointers become None on the same iteration, so a is not b is false and the loop exits returning None — exactly the required answer. Adding null guards exits early and asymmetrically, returning a non-null node that isn't an intersection.
Edge cases
Both pointers eventually hit null on the same step, and the loop exits returning null.
No switch is even needed; the pointers meet at the intersection on the first traversal.
The pointer-swap math still aligns them at that first shared node.