Find the Node Where Two Singly Linked Lists Merge
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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.
Overview: Two singly linked lists stored in one successor array may merge at some node and share every node after it. Given both heads, return the first shared node, or -1 if the lists never meet. It tests linked-list traversal and careful handling of cases such as one list starting inside the other.
Two singly linked lists may merge: from some node onward they share every remaining node. Find the node where they meet.
Both 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`.
**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.
- Every value (labels, list lengths and the answer) fits in a 32-bit signed integer.
**Example 1**
Input: `next_node = [1, 2, 3, -1, 5, 2]`, `head_a = 0`, `head_b = 4`
Output: `2`
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`
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`
List A is `1 -> 2` and list B is `0 -> 1 -> 2`. Node `1`, the head of list A, is the first shared node.
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 (no cycles)
- Every node belongs to list A, list B, or both
- All labels, list lengths and the answer fit in a 32-bit signed integer
Examples
Input: ([1, 2, 3, -1, 5, 2], 0, 4)
Expected Output: 2
Input: ([1, -1, 3, -1], 0, 2)
Expected Output: -1
Hints
- Once two lists share a node, they share everything after it, so both lists end with the same tail. What does that say about how far the merge node is from the end of each list?
- If you knew the length of each list, how could you start two pointers so that they reach the end of their lists at the same moment?
- A simple alternative uses O(n) extra memory: mark every node of one list, then scan the other. Can you avoid the marks?