Intersection of Two Linked Lists
Find where two lists merge by switching pointers between them to cancel out the length difference
Problem Statement
Given the heads of two singly linked lists, return the node at which they intersect. If they never intersect, return null.
Intersection means the two lists share the same node object from some point onward — not merely equal values.
listA: 4 → 1 ↘
8 → 4 → 5
listB: 5 → 6 → 1 ↗
Output: the node with value 8Identity, not equality
Two nodes both holding the value 1 are not an intersection. The lists must converge on one and the same node. Compare with is in Python and === in TypeScript — never by value.
Once the lists meet, they share everything after that point, because each node has a single next pointer.
Intuition
The obstacle is that the lists can have different lengths. If you walk both from their heads in lockstep, the pointers are misaligned — the longer list still has extra nodes to burn through when the shorter one reaches the junction.
There are two clean fixes.
Fix 1 — the hash set (easy to reason about)
Put every node of list A into a set, then walk list B and return the first node already in the set. O(n + m) time, but O(n) memory.
Fix 2 — pointer switching (the elegant one)
The key insight
Let the lists be a + c and b + c long, where c is the shared tail.
Run pointer pA along list A and pointer pB along list B. When either reaches the end, send it to the head of the other list.
pAtravelsa + c, thenb→ totala + c + bpBtravelsb + c, thena→ totalb + c + a
The totals are identical. Both pointers arrive at the junction at the same moment, having each walked every node in both lists exactly once. The length difference cancels itself out without ever being measured.
Real-world analogy
Two people walking each other's routes to work. Route A is 3 km then a shared 2 km; route B is 5 km then the same shared 2 km. If each walks their own route and then immediately starts the other person's, both have walked exactly 10 km — so they arrive at the shared stretch's start together, no matter how unequal the first legs were.
Watch it run
Approach
Loop while they are different nodes
Compare by identity, not by value.
Advance each pointer, redirecting at the end
pA = pA.next if pA else headB, and symmetrically for pB.
Redirecting when the pointer is null (rather than when next is null) is what makes the non-intersecting case terminate.
Return the meeting point
Either the shared node, or null.
Why redirect on `null`, not on `next == null`
If the lists never intersect, both pointers must eventually be null at the same time so the loop can exit. Letting each pointer become null once — after a + b + c steps for both — makes pA == pB == null true simultaneously.
Redirect one step early (if pA.next is None) and the pointers never both hit null, producing an infinite loop on non-intersecting input.
Solution
from typing import Optional
class ListNode:
def __init__(self, val: int = 0, next: Optional["ListNode"] = None):
self.val = val
self.next = next
def get_intersection_node(
head_a: Optional[ListNode], head_b: Optional[ListNode]
) -> Optional[ListNode]:
"""Return the shared node, or None. O(1) space."""
if not head_a or not head_b:
return None
p_a, p_b = head_a, head_b
# Identity comparison: the same node object, not the same value.
while p_a is not p_b:
# Switch lists at the end so both walk a + b + c nodes.
p_a = p_a.next if p_a else head_b
p_b = p_b.next if p_b else head_a
return p_a # the junction, or None if they never meetThe hash-set version, if you prefer something more obvious:
def get_intersection_node_set(
head_a: Optional[ListNode], head_b: Optional[ListNode]
) -> Optional[ListNode]:
seen = set()
node = head_a
while node:
seen.add(id(node)) # identity, not value
node = node.next
node = head_b
while node:
if id(node) in seen:
return node
node = node.next
return NoneComplexity Analysis
Time Complexity
O(n + m)
Space Complexity
O(1)
- Time — each pointer walks at most
n + mnodes before meeting or reachingnulltogether. - Space — two references. The hash-set version is the same time but
O(n)space, which is exactly what the pointer-switching trick eliminates.
Edge Cases
Related Problems
- Linked List Cycle II — another problem solved by pointers that meet at a computed offset
- Middle of the Linked List — two pointers at different speeds
- Merge Two Sorted Lists — walking two lists in step