Find the Node Where Two Linked Lists Intersect
Implement getIntersectionNodeValue
Given the heads of two singly linked lists,
head1 and head2, they may intersect at some node and share every node after that (a "Y" shape) — or they may never intersect at all. Find the value at the first shared node, or return -1 if the lists don't intersect.
Because this exercise is auto-graded by comparing plain output values, the function returns the intersection node's value rather than the node itself — but the algorithm underneath still has to reason about node identity, not value. Two different nodes in two different lists could coincidentally hold the same number without being the same node; the real question is whether the lists ever converge onto literally the same chain of memory.
The brute-force check makes that identity check explicit — for every node of head1, scan all of head2 for a node that is it (not just equals it). The optimal solution reaches the same guarantee in one pass each with a neat trick: walk both lists with one pointer apiece, and whenever a pointer falls off the end of its own list, send it to the other list's head instead of stopping. That head-switchHead-Switch (Two Pointers)When a pointer reaches the end of its own list, redirect it to the other list's head instead of stopping. Both pointers then travel a combined distance of len(head1) + len(head2) by the time they'd reach the intersection, which cancels out any difference in the two lists' unique-prefix lengths — so they arrive at the shared node (or both hit null) on the same step. evens out any difference between the two lists' own lengths, so both pointers arrive at the shared node — or at null, together, if there is none — after at most one switch each.
Example 1:
Input: head1 = [2,8,5], head2 = {"vals":[9,9],"joinAt":1}
Output: 8
Example 2:
Input: head1 = [2,6,4], head2 = {"vals":[1,5],"joinAt":-1}
Output: -1
Example 3:
Input: head1 = [1,2,3], head2 = {"vals":[],"joinAt":0}
Output: 1
+ 5 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ number of nodes unique to head1 or head2 ≤ 10 - ●
0 ≤ number of nodes shared by both lists ≤ 10 - ●
-1000 ≤ node value ≤ 1000 - ●
If the lists intersect, they always share a common tail (a "Y" shape) — once they meet at a node, every node after that is identical in both lists
head1 =
[2, 8, 5]
head2 =
{"vals":[9,9],"joinAt":1}