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.

First Shared Node of Two Merging Lists

Hints

1. 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?
2. 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?
3. A simple alternative uses O(n) extra memory: mark every node of one list, then scan the other. Can you avoid the marks?

Approach

Because each node has a single successor, two lists that ever share a node share every node after it, so they end with a common tail. The merge node therefore sits at the same distance from the end of both lists. The reference first walks each list to count its length, then advances the pointer on the longer list by the difference so both pointers are equally far from the end. It then moves the two pointers one step at a time in lockstep: the first node where they coincide is the first shared node. If the lists are disjoint, both pointers reach -1 on the same step and the loop returns -1. When head_a == head_b the lengths are equal and the loop exits immediately with head_a. Each list is traversed at most twice, and only a few integer variables are used. An equivalent O(n)-space approach marks every node of list B in a boolean array and returns the first node of list A that is marked.

• Time complexity: O(n)
• Space complexity: O(1)