Community Problem
Intersection of Two Linked Lists
Difficulty: Easy
Find the node where two singly-linked lists merge using the two-pointer rendezvous trick that runs in O(m + n) time and O(1) space.
Intersection of Two Linked Lists
Find the node where two singly-linked lists merge using the two-pointer rendezvous trick that runs in O(m + n) time and O(1) space.
By @folakemansour
March 1, 2026
·
Updated May 18, 2026
709 views
4
Rate
I rotate this in for fast/slow + linked-list onsite practice because the two-pointer rendezvous trick is the kind of idea that's hard to derive from scratch in 30 minutes. The hash-set version (store all nodes from list A, scan B looking for the first hit) is the easy answer; the senior signal is the constant-space pointer-swap pattern.
Intersection of Two Linked Lists
Given the heads headA and headB of two singly-linked lists that may merge at some node, return the node at which the two lists first intersect. If the lists do not intersect, return null. Intersection is by reference, not by value: two nodes are the same intersection only if they are the same node object in memory.
After the intersection node, the two lists share the same tail (because each node has only one next reference). Before the intersection node, the two lists may have different lengths.
Examples
Example 1:
- Input: list A =
[4, 1, 8, 4, 5], list B =[5, 6, 1, 8, 4, 5], with the merge happening at the node with value8. - Output: node with value
8 - Explanation: After
4, 1in A and5, 6, 1in B, both walk into the same8 -> 4 -> 5tail.
Example 2:
- Input: list A =
[1, 9, 1, 2, 4], list B =[3, 2, 4], merge at node value2. - Output: node with value
2 - Explanation: A's tail
2 -> 4is the same as B's tail2 -> 4.
Example 3:
- Input: list A =
[2, 6, 4], list B =[1, 5], no intersection. - Output:
null - Explanation: Disjoint lists.
Example 4:
- Input: list A =
[1], list B =[1], no intersection (separate single nodes). - Output:
null - Explanation: Two distinct single-node lists, even with equal values.
Constraints
- The number of nodes in list A is in the range
[1, 3 * 10^4]. - The number of nodes in list B is in the range
[1, 3 * 10^4]. 1 <= Node.val <= 10^5- The lists may or may not intersect, but if they do they share the same tail.
Follow-up
Can you do it in O(m + n) time and O(1) extra space? The pointer-swap trick is what gets you there.
Solution
Hints
Approach
The naive O(m + n) time, O(m) space solution uses a hash set: store every node from list A, then walk list B and return the first node already in the set. The follow-up asks for O(1) space, which the two-pointer pointer-swap pattern achieves.
Key insight
If list A has length m and list B has length n, walking both pointers and switching to the other head when each one hits null aligns them. After exactly m + n total steps, both pointers have walked the SAME total distance (m + n from their respective starting heads), so they end up at the same offset from the combined tail. If the lists share a tail, that aligned offset is the intersection node. If they do not, both pointers become null at the same step.
Algorithm
- Edge case: if either head is null, return null.
pA = headA,pB = headB.- While
pA !== pB:pA = pA === null ? headB : pA.next.pB = pB === null ? headA : pB.next.
- Return
pA(which equalspB, either the intersection node or bothnull).
Complexity
Metric Value
------ -----------
Time O(m + n)
Space O(1)Each pointer advances at most m + n times (the full traversal length once on each side), so the total work is bounded.
Why it works
Let a and b be the lengths of the unique prefixes of lists A and B before the intersection, and c be the length of the shared tail (so m = a + c and n = b + c). Walking pA along A then jumping to B traverses a + c + b nodes before reaching the intersection. Symmetrically pB traverses b + c + a. Both totals equal a + b + c, so both pointers arrive at the intersection node simultaneously.
When the lists do not intersect (c = 0 and they end at distinct nulls), pA traverses a + b and pB traverses b + a, both then advance to null at the same step. The loop exits with pA == pB == null, which we return.
Pitfalls
- Using
pA.next === null ? ... : ...instead ofpA === null ? ... : .... The cleaner formulation jumps when the pointer itself is null, which lets the no-intersection case terminate gracefully. - Comparing
.valinstead of node identity. Two nodes with the same value are NOT the same node. Use===(JS) oris(Python). - Forgetting the null-head guards at the top. If either head is null, the loop would never terminate because both pointers would oscillate between null and the other head's first node.
Solution Code