Intersection of Two Linked Lists
Last Updated: April 1, 2026
Understanding the Problem
This problem asks us to find the point where two linked lists merge into a single shared tail. It's important to understand what "intersection" means here: it's about identity, not value. Two nodes intersect if they are literally the same node in memory, not just two different nodes that happen to hold the same value. Once two lists converge at an intersection node, they share every subsequent node all the way to the end.
The main challenge is that the two lists can have different lengths. If list A has 5 nodes before the intersection and list B has 3, simply walking both pointers forward in lockstep won't line them up. So the core question becomes: how do we synchronize two pointers that start at different distances from the intersection point?
Key Constraints:
1 <= m, n <= 3 * 10^4→ With up to 30,000 nodes per list, O(m * n) would mean nearly a billion operations, which is too slow. We should aim for O(m + n).1 <= Node.val <= 10^5→ Values are positive integers, but remember that intersection is about node identity, not node values. Two nodes with value 8 are not the same unless they're the same object.- The follow-up explicitly asks for O(m + n) time and O(1) space, which tells us the interviewer expects something better than a hash set.
Approach 1: Hash Set
Intuition
The most natural first idea: if you could quickly check whether a node from list B also appears in list A, you'd find the intersection. A hash set gives us O(1) lookups. Walk through all of list A and store every node reference in a set. Then walk through list B and check each node against the set. The first node found in the set is the intersection point.
This is straightforward and correct. The only downside is that it uses O(m) extra space for the set, which doesn't satisfy the follow-up constraint.
Algorithm
- Create an empty hash set.
- Traverse list A from head to tail. For each node, add the node reference to the set.
- Traverse list B from head to tail. For each node, check if it exists in the set.
- The first node in list B that exists in the set is the intersection node. Return it.
- If no node from list B is found in the set, the lists don't intersect. Return null.
Example Walkthrough
Input:
Pass 1: Store all listA nodes in a set. Pass 2: Walk listB, checking each node. The first three nodes (5, 6, 1) are unique to listB and not in the set. Node 8 is a shared node and IS in the set:
Code
- Time Complexity: O(m + n). We traverse list A once (m nodes) to build the set, then traverse list B once (n nodes) to check membership. Each set operation is O(1) average.
- Space Complexity: O(m). We store all m nodes from list A in the hash set.
This approach works correctly but uses O(m) extra space. What if we could align the two pointers so they arrive at the intersection simultaneously, without storing any nodes at all?
Approach 2: Two Pointers
Intuition
Here's the elegant trick that makes this problem a classic. The two lists have different lengths, so if you start two pointers at their respective heads and walk forward, they won't reach the intersection at the same time. But what if each pointer, upon reaching the end of its list, continues from the head of the other list?
Think about the total distance each pointer travels. Pointer A walks through list A (length m), then switches to list B (length n). Pointer B walks through list B (length n), then switches to list A (length m). Both pointers travel exactly m + n nodes total. The key insight is that the difference in lengths gets absorbed during the first pass. On the second pass, both pointers are the same distance from the intersection point, so they meet exactly there.
If there's no intersection, both pointers reach null at the same time after traveling m + n nodes each.
The beauty of this approach is in the symmetry. Let's call the unique portion of list A "a" nodes, the unique portion of list B "b" nodes, and the shared tail "c" nodes. Pointer A travels: a + c + b nodes before reaching the intersection on its second pass. Pointer B travels: b + c + a nodes before reaching the intersection on its second pass. Since a + c + b = b + c + a, both pointers arrive at the same node at the same time.
If there's no intersection (c = 0), pointer A travels a + b nodes and reaches null, while pointer B travels b + a nodes and also reaches null. Since null == null, the loop terminates and we return null. The algorithm handles both cases naturally without any special checks.
Algorithm
- Initialize pointer
pAatheadAand pointerpBatheadB. - Walk both pointers forward one node at a time.
- When
pAreaches the end of list A (null), redirect it toheadB. - When
pBreaches the end of list B (null), redirect it toheadA. - If the lists intersect,
pAandpBwill meet at the intersection node. - If they don't intersect, both will reach null at the same time. Return null.
Example Walkthrough
Code
- Time Complexity: O(m + n). Each pointer traverses at most m + n nodes (one full pass through each list). The loop runs at most m + n iterations.
- Space Complexity: O(1). Only two pointer variables are used, regardless of list sizes.