DSA Tracker

Visualize

Intersection of Two Linked Lists

Two pointers that swap lists at the end walk equal distances

time O(m + n)space O(1)

Two lists that merge share every node from the join onward, but their parts BEFORE the join can differ in length, so two pointers stepping together from the two heads are out of phase and never coincide. The trick is to let each pointer, on reaching the end of its list, continue from the head of the other list. Then both pointers travel exactly the same total distance (A's part + B's part + the shared tail) before arriving at the join, so on that second lap they hit the first shared node on the same step. If the lists never meet, both pointers reach NULL together after the same distance, and the loop ends returning NULL. The row below shows A's own nodes, then B's own nodes, then the shared tail once.

Details

Animated on: listA = [4,1,8,4,5], listB = [5,6,1,8,4,5]. The two lists share the same tail nodes 8 -> 4 -> 5 (same objects, not just equal values). Return the node where they first join. Answer: the node with value 8.

Problem:Intersection of Two Linked ListsEasy

Pattern:Fast and Slow Pointers

Two pointers that swap lists at the end walk equal distances

step 1 / 10

A:4
[0]
A:1
[1]
B:5
[2]
B:6
[3]
B:1
[4]
8
[5]
4
[6]
5
[7]

List A has 2 nodes of its own, list B has 3, and both then run into the same 3-node tail (tinted). pA starts at A's head and pB at B's head. A and B have different lengths, so walking them in lockstep would never line the two pointers up on the shared node — unless each pointer also walks the OTHER list, which makes both trips exactly 2 + 3 + 3 nodes long.

  • pA=0· arr[0] = A:4
  • pB=2· arr[2] = B:5
Pseudocode
1FUNCTION intersection(headA, headB)
2  pA <- headA
3  pB <- headB
4  WHILE pA != pB
5    IF pA = NULL
6      pA <- headB
7    ELSE
8      pA <- NEXT(pA)
9    IF pB = NULL
10      pB <- headA
11    ELSE
12      pB <- NEXT(pB)
13  RETURN pA

← / → step · space play · Home restart

Every step in words

Show all 10 steps
  1. List A has 2 nodes of its own, list B has 3, and both then run into the same 3-node tail (tinted). pA starts at A's head and pB at B's head. A and B have different lengths, so walking them in lockstep would never line the two pointers up on the shared node — unless each pointer also walks the OTHER list, which makes both trips exactly 2 + 3 + 3 nodes long.
  2. pA -> A:1; pB -> B:6. Still different nodes after 1 step, so keep going.
  3. pA -> 8; pB -> B:1. Still different nodes after 2 steps, so keep going. pA is already in the shared tail while pB is still on B's own nodes: A's part is 1 shorter, and that gap is exactly what lockstep walking can never close.
  4. pA -> 4; pB -> 8. Still different nodes after 3 steps, so keep going.
  5. pA -> 5; pB -> 4. Still different nodes after 4 steps, so keep going.
  6. pA steps off the end of its list to NULL; pB -> 5. Still different nodes after 5 steps, so keep going.
  7. pA was at NULL, so it restarts at B's head (B:5); pB steps off the end of its list to NULL. Still different nodes after 6 steps, so keep going. The restart is the whole trick: the pointer that finished first now has to walk the other list's part, so by the time both are on their second list they have covered the same distance.
  8. pA -> B:6; pB was at NULL, so it restarts at A's head (A:4). Still different nodes after 7 steps, so keep going.
  9. pA -> B:1; pB -> A:1. Still different nodes after 8 steps, so keep going.
  10. Both pointers land on the same node object, value 8. Each has now walked exactly 9 steps — its own prefix, the tail, the other prefix — so the length difference has cancelled out and they meet at the first shared node.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Intersection of Two Linked Lists in the editorAll Linked List problemsBack to roadmap