158. Intersection of Two Linked Lists
You are given the heads of two singly linked lists, headA and headB. Somewhere down the line the lists may merge: from one node onward they consist of the very same nodes — identical objects in memory, not merely nodes holding equal values. Once merged they never split apart again, and neither list contains a cycle.
The function receives the two head nodes and returns the first node the lists share, or null when they never meet. Equal values prove nothing: two different nodes can carry the same value, so comparisons must be by node identity, not by value. The lists must be left exactly as they were found.
The judged output is the value stored at the returned node, or the word null when no shared node exists. Aim for O(m + n) time with O(1) extra memory.
Example 1:
Input: listA = [4, 1, 8, 4, 5], listB = [5, 6, 1, 8, 4, 5], merging at the node with value 8
Output: the node holding 8
Explanation: List A runs 4 → 1 → 8 → 4 → 5 and list B runs 5 → 6 → 1 → 8 → 4 → 5, where the nodes 8 → 4 → 5 are shared objects. The first shared node holds 8. Note the value 1 appears in both lists earlier without being a shared node.
Example 2:
Input: listA = [2, 6, 4], listB = [1, 5], no shared nodes
Output: null
Explanation: The two lists never share a node, so there is nothing to return.
Constraints:
- 1 ≤ length of each list ≤ 10⁴
- -10⁵ ≤ Node.val ≤ 10⁵
- The lists contain no cycles.
- If the lists intersect, they share every node from the intersection onward.
- The lists must keep their original structure after the function returns.
Hints:
Matching values are a red herring — different nodes can hold the same value. You need node identity, and remembering every node of one list in a hash set gives you an identity test in O(1).
If you knew both lengths, you could advance a pointer along the longer list by the difference first, then walk the two pointers in lockstep until they collide.
For the elegant O(1)-space version: run pointer a through list A then list B, and pointer b through list B then list A. Both cover m + n steps, so they reach the merge node — or the end — at the same moment.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: listA = [4, 1, 8, 4, 5], listB = [5, 6, 1, 8, 4, 5] — merging at the node with value 8
Expected output: 8