Find the Node Where Two Singly Linked Lists Merge

Two singly linked lists may merge: from some node onward, they share every remaining node. Find the node where they meet.

The lists are stored together in one successor array. Nodes are labeled 0 to n - 1, and next_node[i] is the label of the node that follows node i, or -1 if node i is the last node of its list. List A starts at node head_a and list B starts at node head_b; each list is the sequence of nodes visited by following next_node from its head until reaching -1.

Return the label of the first node of list A that also belongs to list B. If the two lists share no node, return -1.

Function Signature

def first_shared_node(next_node: list[int], head_a: int, head_b: int) -> int:

Rules

• Nodes are compared by label: two nodes are shared only if they are the same node.
• Because every node has exactly one successor, once the two lists share a node they share every node after it. The first node of list A that belongs to list B is therefore also the first node of list B that belongs to list A, so the answer is unique.
• If head_a == head_b, the lists are identical and the answer is head_a.

Constraints

• 1 <= n <= 100000, where n = len(next_node)
• -1 <= next_node[i] <= n - 1 and next_node[i] != i
• 0 <= head_a <= n - 1 and 0 <= head_b <= n - 1
• Following next_node from head_a or from head_b reaches -1 without visiting any node twice, so neither list has a cycle.
• Every node belongs to list A, list B, or both.

Examples

Example 1

• Input: next_node = [1, 2, 3, -1, 5, 2], head_a = 0, head_b = 4
• Output: 2
• Explanation: List A is 0 -> 1 -> 2 -> 3 and list B is 4 -> 5 -> 2 -> 3. They merge at node 2.

Example 2

• Input: next_node = [1, -1, 3, -1], head_a = 0, head_b = 2
• Output: -1
• Explanation: List A is 0 -> 1 and list B is 2 -> 3. They share no node.

Example 3

• Input: next_node = [1, 2, -1], head_a = 1, head_b = 0
• Output: 1
• Explanation: List A is 1 -> 2 and list B is 0 -> 1 -> 2. Node 1, the head of list A, is the first shared node.