Flatten a Multilevel Doubly Linked List

Implement flattenMultilevel

Given several doubly linked lists and a description of which node in which list each of the other lists hangs off of as a "child" list, flatten the whole structure into a single doubly linked list — visiting a node, then diving into its entire child subtree, then continuing to its own next node — and return the head. A child list can itself have a node with its own child list, nested arbitrarily deep — so this isn't a one-level splice. The recursive approach handles that naturally: flattening a node's child fully (however deep it goes) before splicing it in is exactly what a depth-first recursive call does, with no extra bookkeeping needed to track "how many levels deep" the walk currently is.

Example 1:

Input: lists = [[4,8,3,15],[7,12],[9]], childOf = [[0,1],[1,0]]

Output: [4,8,7,9,12,3,15]

Example 2:

Input: lists = [[2,5,9]], childOf = []

Output: [2,5,9]

Example 3:

Input: lists = [[1,3],[2]], childOf = [[0,0]]

Output: [1,2,3]

+ 5 hidden test cases run on Submit.

Constraints:

  • 0 ≤ number of lists ≤ 50
  • 0 ≤ total nodes across every list ≤ 200
  • -1000 ≤ node value ≤ 1000
  • a list may attach as a child of any node in any other list — including another child list — so nesting depth is not bounded to one level

lists =

[[4,8,3,15], [7,12], [9]]

childOf =

[[0,1], [1,0]]