Find the Intersection Node of Two Linked Lists
LinkedIn● EasyFULLTIMEPHONE SCREENProblem statement
Two acyclic singly linked lists are stored in one node table. Node i points to node next[i]; a value of -1 means that the node has no successor. The integers headA and headB are the head-node indices, or -1 for an empty list.
Return the index of the first node that is reachable from both heads. Intersection is based on node identity, not equal values. Once the lists reach the same node, they share the remaining suffix. Return -1 if they do not intersect.
Function
findIntersectionNode(next: int[], headA: int, headB: int) → intExamples
Example 1
next = [1,2,3,-1,2]headA = 0headB = 4return = 2The first list follows 0 -> 1 -> 2 -> 3, while the second follows 4 -> 2 -> 3. Their first shared node is index 2.
Example 2
next = [1,-1,3,-1]headA = 0headB = 2return = -1The two chains end separately, so there is no shared node.
Example 3
next = [1,2,-1]headA = 0headB = 0return = 0Both lists start at the same node, so that head is the intersection.
Constraints
0 <= next.length <= 200000- Every entry of
nextis-1or a valid node index. - Each chain reachable from
headAorheadBis acyclic. - Each head is
-1or a valid node index.