Intersection of Two Linked Lists
Understanding the Problem
This problem asks us to find the point where two linked lists merge into a single shared tail. Intersection here means identity, not value. Two nodes intersect when they are the same node in memory, not two different nodes that happen to hold the same value. Once two lists converge at an intersection node, they share every node from there 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, walking both pointers forward in lockstep will not line them up. The core question becomes how to 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 asks for O(m + n) time and O(1) space, which rules out storing nodes in a hash set.
Approach 1: Hash Set
Intuition
If we record every node from one list, then checking whether a node from the other list was already seen becomes an O(1) lookup. A hash set provides that lookup. 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, because from that node onward both lists share the same nodes.
This is correct but uses O(m) extra space for the set, which does not 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:
In this example the two lists merge at the node with value 8, so listA is 4 -> 1 -> 8 -> 4 -> 5 and listB is 5 -> 6 -> 1 -> 8 -> 4 -> 5, where the trailing 8 -> 4 -> 5 is the shared tail.
Pass 1 stores all five listA nodes in the set. Pass 2 walks listB and checks each node against the set. The first three nodes (5, 6, 1) belong only to listB and are not in the set. The next node is the shared node 8, which is in the set, so we return it immediately:
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. The next approach aligns two pointers so they arrive at the intersection at the same time, without storing any nodes.
Approach 2: Two Pointers
Intuition
The two lists have different lengths, so two pointers starting at their respective heads and walking forward in lockstep will not reach the intersection at the same time. The fix is to have each pointer, upon reaching the end of its list, continue from the head of the other list.
Consider 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 difference in lengths is absorbed during the first pass. On the second pass, both pointers are the same distance from the intersection point, so they meet there.
If there's no intersection, both pointers reach null at the same time after traveling m + n nodes each.
Let the portion of list A before the intersection be a nodes, the portion of list B before the intersection be b nodes, and the shared tail be 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 it. Since a + c + b = b + c + a, both pointers arrive at the same node after the same number of steps.
When there is no intersection, c = 0. Pointer A travels a + b nodes and reaches null; pointer B travels b + a nodes and also reaches null. The two pointers become equal (both null) at that point, the loop condition pA != pB becomes false, and we return null. Both cases use the same loop with no special-casing.
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.