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 ```python 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.