First Node Two Linked Lists Share
Problem statement
The nodes of two singly linked lists are numbered 0 to n - 1. You get them as a link table: link[i] is the number of the node that comes right after node i, or -1 if node i is the last node of its list.
List A starts at node headA and list B starts at node headB. The two lists may join: once they reach a common node, everything after it is shared too.
Return the number of the first node that is on both lists. If the lists share no node, return -1. If headA equals headB, that node is the answer.
Function
firstSharedNode(link: int[], headA: int, headB: int) → intExamples
Example 1
link = [4,3,-1,2,2]headA = 0headB = 1return = 2List A is 0 → 4 → 2 and list B is 1 → 3 → 2. Both reach node 2, and from there they share everything, so the answer is 2.
Example 2
link = [1,-1,3,-1]headA = 0headB = 2return = -1List A is 0 → 1 and list B is 2 → 3. They have no node in common, so the answer is -1.
Example 3
link = [1,2,-1]headA = 1headB = 0return = 1List A starts at node 1 (1 → 2) and list B is 0 → 1 → 2. List A's first node is already on list B, so they meet at node 1.
Constraints
1 <= link.length <= 10^4-1 <= link[i] < link.length0 <= headA, headB < link.length- Every node is on list A, list B, or both, and neither list has a cycle.