55. Intersection of Two Linked Lists
Determine whether the two lists eventually join into the same chain of node objects. If they do, return the first node belonging to both traversals.
Intersection is about object identity. Two separate nodes containing the same value do not intersect, and neither input list may be modified.
Example 1
Input
A0→A1→C0→C1; B0→C0→C1
Output
C0
Explanation: The fixture must use the same C0 and C1 objects from both heads; copying equal values does not create sharing.
Example 2
Input
A0(7)→A1(9); B0(7)→B1(9), all distinct
Output
null
Explanation: The value sequences are equal but no reference is shared.
Example 3
Input
Both heads are C0
Output
C0
Explanation: Initial pointer identity already identifies the first shared object.
Constraints
0 <= nodes per input list <= 105-231 <= node.value <= 231 - 1- Lists are acyclic and may share a suffix. Intersection means the same node object.
Hints
Hint 1
If lengths were known, you could align the remaining distances to the end.
Hint 2
Can each pointer traverse both lists so their total distances agree?
Hint 3
Advance normally, switch a null pointer to the other head, and stop when p==q, possibly at null.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Unequal prefixes converge on one shared suffix
[4,1]
[9,2,3]
[8,8]
"S0"