Find a Linked-List Intersection by Identity
Problem statement
Two singly linked lists are represented by node identities0..n-1 and a shared link table next. Entry next[i] is the identity of node i successor, or-1 for null. The heads may reach the same tail nodes. Return the identity of their first shared node, or-1 if they are disjoint. Identity, not an equal payload value, establishes intersection. Leave all links unchanged; unused table entries do not affect the answer.
Function
intersectionNode(next: int[], headA: int, headB: int) → intExamples
Example 1
next = [2,3,4,4,-1]headA = 0headB = 1return = 4The paths are0→2→4 and1→3→4, so their first common identity is4.
Example 2
next = [1,-1,3,-1]headA = 0headB = 2return = -1The paths0→1 and2→3 contain no shared node identity.
Constraints
0 <= next.length <= 500.-1 <= next[i] <= 499.-1 <= headA <= 499.-1 <= headB <= 499.- Every next entry and head is either -1 or a node index less than next.length; following links from either head reaches -1 without a cycle.