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]]