Find the Intersection of Two Linked Chains

A singly linked structure is represented by an array `next_node`, where `next_node[i]` is the next node index or `-1` for the end. Two acyclic chains begin at `head_a` and `head_b`. Once the chains reach the same node index, they share the entire remaining suffix. Implement: ```text first_intersection( next_node: List[int], head_a: int, head_b: int ) -> int ``` Return the first node index shared by both chains, or `-1` if they do not intersect. ### Constraints - `0 <= len(next_node) <= 200_000` - Each head is `-1` or a valid node index. - Every nonnegative `next_node[i]` is a valid index. - The reachable chains are acyclic. - Target (O(a+b)) time and (O(1)) extra space, where (a) and (b) are chain lengths. ### Clarifications - Intersection means identical node index, not equal stored values. - Either head may be `-1`. - If both heads are the same valid index, return that index immediately. ```hint Equalize the traversed distance When a pointer reaches the end of one chain, redirect it to the other chain's head. Both pointers then traverse equal combined distances before meeting or reaching the end. ``` ### Examples ```text Input: next_node = [1, 2, -1, 2], head_a = 0, head_b = 3 Output: 2 Input: next_node = [1, -1, 3, -1], head_a = 0, head_b = 2 Output: -1 ``` ### Evaluation Focus - Node identity rather than value comparison. - Correct two-pointer termination for intersecting and disjoint chains. - Empty heads and unequal chain lengths. - Constant auxiliary space without marking visited nodes. ### Extension How would you detect and handle cycles if the acyclic guarantee were removed?