On this page
Description
Two singly linked lists intersect when, from some node on, they share the very same nodes: a Y shape. Finding that first shared node is easy with a hash set. It's also possible in O(1) space with two pointers. Either measure both lengths and give the longer list a head start, or let each pointer jump to the other list's head when it runs out. Then both walk the same total distance and meet at the junction.
We'll go from simple to more technical:
- The pattern: two pointers that switch lists when they reach the end.
- A second flavor: count the lengths, then align the starts.
- Where finding the point two chains converge shows up in practice.
- The traps: comparing values instead of nodes, and assuming equal lengths.
The approach
The two lists usually have different lengths before they meet. So walking both from their heads, one step at a time, doesn't line up the shared part. Here's the fix. Walk pointer a along list A and pointer b along list B. When a pointer runs off the end, jump it to the head of the other list. Now each pointer walks both lists' private parts plus the shared part once. They cover the same total distance, so they reach the junction at the same moment.
List A is 3 -> 7 -> 2 -> 9 and list B is 5 -> 2 -> 9, where both lists share the same 2 node:
| Step | a | b |
|---|---|---|
| Start | 3 | 5 |
| 1 | 7 | 2 |
| 2 | 2 | 9 |
| 3 | 9 | null |
| 4 | null | 3 (jumped to A's head) |
| 5 | 5 (jumped to B's head) | 7 |
| 6 | 2 | 2: the same node, so stop |
Java
ListNode a = headA, b = headB;
while (a != b) {
a = (a == null) ? headB : a.next;
b = (b == null) ? headA : b.next;
}
return a; // the intersection node, or null if the lists never intersect
Python
def get_intersection_node(head_a: ListNode | None, head_b: ListNode | None) -> ListNode | None:
a, b = head_a, head_b
while a is not b:
a = head_b if a is None else a.next
b = head_a if b is None else b.next
return a # the intersection node, or None if the lists never intersect
If the lists never meet, both pointers reach null at the same time after walking both lists, and the loop returns null.
A second flavor: count the lengths, then align
The same idea can be made explicit. Measure both lengths. Move the longer list's pointer ahead by the difference, so both pointers are the same distance from the end. Then walk them together until they meet:
Java
int lenA = length(headA), lenB = length(headB);
ListNode a = headA, b = headB;
// advance the longer list's pointer by the difference, so both have
// the same remaining distance left to the end
for (int i = 0; i < lenA - lenB; i++) a = a.next;
for (int i = 0; i < lenB - lenA; i++) b = b.next;
while (a != b) {
a = a.next;
b = b.next;
}
return a;
Python
def get_intersection_node(head_a: ListNode | None, head_b: ListNode | None) -> ListNode | None:
len_a, len_b = length(head_a), length(head_b)
a, b = head_a, head_b
# advance the longer list's pointer by the difference, so both have
# the same remaining distance left to the end
for _ in range(len_a - len_b):
a = a.next
for _ in range(len_b - len_a):
b = b.next
while a is not b:
a = a.next
b = b.next
return a
This walks each list once more to measure it, but some readers find the alignment easier to trust. Both versions rest on the same fact: two pointers the same distance from the end, moving together, reach the shared part at the same time.
Where you'll see it
Version histories work like this. Two branches of a repository each point back to their parent commit, and they meet at a shared ancestor. Finding where two chains of references converge, without knowing their lengths, is the same walk.
Which tool for which job?
| You need | Use |
|---|---|
| The junction, simplest code | a hash set of one list's nodes |
| The junction in O(1) space | switch pointers, or count and align |
| The junction when lists may contain cycles | detect cycles first (Floyd), then compare entrances |
| Whether two nodes are the same node | == on references (Java), is (Python) |
| Whether two lists hold the same values | compare values while walking |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
Comparing values (val ==) | matches unrelated nodes with equal values | compare references |
equals on a record node / == on a dataclass node | compares whole tails, deeply - and can overflow the stack | == on references in Java, is in Python |
| Walking both lists in lockstep from the heads | misses the junction when lengths differ | switch pointers, or align first |
| Switching more than once | an endless loop with no junction | switch once; both reach null together |
| Running it on lists with cycles | never terminates | check for cycles first |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Two nodes in two different lists hold the same value. Does a.val == b.val mean the lists intersect?
Show answer
No. Intersecting means sharing the same node object from some point on. Compare references, == in Java or is in Python. Two unrelated nodes can easily hold equal values.
2. Why does walking both lists from their heads, without switching, miss the junction?
Show answer
With different lengths, the pointers are always the same distance from their own heads, not from the shared part. So they compare unrelated nodes and pass the junction at different times. It only works when both lists happen to be the same length.
3. Why does switching to the other list's head make the pointers meet at the junction?
Show answer
Each pointer walks its own private part, then the other list's private part, then reaches the shared part. That's the same total distance for both. So they arrive at the first shared node on the same step, or both reach null if there's no shared part.
Key takeaways
- Intersecting means sharing the same node. Compare references, never values.
- Walking from both heads in step only works when the lengths match.
- Jumping each pointer to the other list's head makes both walk the same distance, so they meet at the junction.
- Counting both lengths and giving the longer list a head start works too, at the cost of an extra pass.