Intersection of Two Linked Lists is a classic two-pointer puzzle. Two singly-linked lists may merge and share a tail — together they form a Y shape. The task is to find the exact node where they join, ideally in one pass and no extra memory.
Problem. You are given the heads of two singly-linked lists, headA and headB. The lists may
intersect: from some node onward they share the same nodes (same objects in memory, not just equal
values). Return that first shared node, or None if they never intersect.
Example: list A is 4 → 1 → 8 → 5 and list B is 5 → 6 → 8 → 5, where the 8 → 5 tail is the same
two nodes. The answer is the node 8 — the point where the Y joins.
The slow way first
The brute-force idea: for every node in A, walk all of B looking for the same node object. That is O(m × n) time. A faster fix uses a hash set — store every node of A, then scan B until you hit one that is already in the set. That is O(m + n) time but costs O(m) extra memory for the set.
The question to ask: can I align the two pointers so they arrive at the join at the same moment — without any extra storage?
The idea: swap lists at the end
The two lists have different lengths before the merge, so a naive "advance both by one" never lines them up. The trick fixes that: when a pointer reaches the end of its list, send it to the head of the other list.
Why it works: pointer a walks lenA nodes, then lenB nodes — total lenA + lenB. Pointer b walks lenB then lenA — the same total. After at most lenA + lenB steps they have travelled equal distance, so they land on the shared node together (or both reach None together if the lists never intersect).
The elegant part: you never compute the lengths. The list-swap does the alignment for you.
Walk through it
Step through the animation. Pointer a (blue) starts on headA, pointer b (red) on headB. Each step both advance one node. When b falls off the end it jumps to headA; when a falls off it jumps to headB. After the swap they march in lockstep and meet exactly at the shared node 8, which lights up green.
Pseudocode
a = headA
b = headB
while a is not the same node as b:
if a has a next: a = a.next else: a = headB # jump to the OTHER head
if b has a next: b = b.next else: b = headA
return a # the shared node, or None if both ended togetherThe Python solution
def get_intersection(headA, headB):
a, b = headA, headB
while a is not b:
# step a; at the end, jump to headB
a = a.next if a else headB
# step b; at the end, jump to headA
b = b.next if b else headA
return a # the shared node, or Nonea, b = headA, headBputs one pointer on each list head.while a is not buses identity (is), not value equality — two different nodes can hold the same number, so we compare the objects themselves.a = a.next if a else headBadvancesa; onceabecomesNone(ran past the end), the next iteration sends it toheadB.- The mirror line does the same for
b, jumping toheadA. - The loop ends either when both point at the shared node, or when both are
Noneat the same time — in which caseaisNone, the correct "no intersection" answer.
Complexity
| Case | Time | Notes |
|---|---|---|
| Brute force (node vs node) | O(m * n) (moderate) | scan B for every node of A |
| Hash set of A | O(m + n) (moderate) | but O(m) extra memory |
| Two pointers (this solution) | O(m + n) (moderate) | each walks lenA + lenB |
O(1) (fast)The two-pointer version matches the hash-set time but uses no extra space — just two pointers. That O(1) memory is what makes it the interview-favorite answer.
When this pattern shows up
Whenever two sequences have different lengths but you need them aligned, look for a way to make each traverse the same total distance. Swapping to the other list at the end is the linked-list version; the same align-by-equal-travel idea appears in cycle detection and in merging problems.
Compare nodes by identity, not value. Using a.val == b.val would falsely report an intersection
whenever two unrelated nodes happen to share a number. And let a pointer reach None before redirecting
it — that one extra None step is what handles the no-intersection case and stops an infinite loop.
Practice
List A has length 5 and list B has length 4. How many total nodes does pointer a visit before it can possibly meet pointer b?
1. Why does each pointer jump to the other list head at the end?
2. How should the two pointers be compared?
3. What is the extra space used by the two-pointer solution?
4. What happens if the two lists never intersect?