Flatten a Linked List with Nested Side Branches into One Doubly Linked List

A singly linked list becomes a doubly linked list once every node also links back to its predecessor. This problem extends that conversion. Besides its forward link, any node may carry at most one side branch: a link to the first node of another list. Nodes inside a branch list may carry side branches of their own, so the whole structure is shaped like a binary tree whose root is the head of the main list.

Flatten the structure into one doubly linked list by splicing every side branch in between its parent node and the node that originally followed the parent. Branches nested inside a branch are spliced in the same way, before the rest of the enclosing branch continues.

The nodes are stored in two arrays. Nodes are labeled 0 to n - 1, and node 0 is the head of the main list. next_node[i] is the node that follows node i in its own list, or -1 if node i is the last node of its list. branch[i] is the first node of node i's side branch, or -1 if node i has no side branch.

Return the flattened doubly linked list as two arrays of length n: result[0][i] is the node that comes after node i in the flattened list (-1 for the last node), and result[1][i] is the node that comes before node i (-1 for node 0).

Function Signature

def flatten_with_branches(next_node: list[int], branch: list[int]) -> list[list[int]]:

Rules

• In the flattened list, every node is immediately followed by the flattened contents of its side branch, if it has one, and after that by the flattened remainder of the list that originally followed it.
• Node 0 is the first node of the flattened list, and every node appears in it exactly once.
• If no node has a side branch, the flattened list is the main list in its original order, now with backward links. This is the plain singly-to-doubly conversion.
• Side branches do not appear in the output: after flattening, nodes are connected only by their forward and backward links.
• Return exactly two arrays: forward links first, backward links second.

Constraints

• 1 <= n <= 100000, where n = len(next_node) = len(branch)
• -1 <= next_node[i] <= n - 1 and -1 <= branch[i] <= n - 1
• Node 0 is referenced by no entry of next_node or branch. Every other node is referenced by exactly one entry across the two arrays, and every node can be reached from node 0 by following next_node and branch links. The structure therefore has no cycles and no shared nodes.
• Branches may be nested, and the nesting depth can be as large as n - 1.
• The output is uniquely determined by the input.

Examples

Example 1

• Input: next_node = [1, 2, -1], branch = [-1, -1, -1]
• Output: [[1, 2, -1], [-1, 0, 1]]
• Explanation: There are no side branches. The list 0 -> 1 -> 2 keeps its order and gains backward links.

Example 2

• Input: next_node = [1, 2, -1, 4, -1, -1], branch = [-1, 3, -1, 5, -1, -1]
• Output: [[1, 3, -1, 5, 2, 4], [-1, 0, 4, 1, 5, 3]]
• Explanation: The main list is 0 -> 1 -> 2. Node 1 has the side branch 3 -> 4, and node 3 has the side branch 5. The flattened list is 0 -> 1 -> 3 -> 5 -> 4 -> 2: node 3's branch comes right after node 3, then the rest of node 1's branch (node 4), then the rest of the main list (node 2).

Example 3

• Input: next_node = [1, -1, 3, -1], branch = [-1, 2, -1, -1]
• Output: [[1, 2, 3, -1], [-1, 0, 1, 2]]
• Explanation: Node 1 is the last node of the main list and has the side branch 2 -> 3, so the branch simply extends the list: 0 -> 1 -> 2 -> 3.