Flatten a Multilevel Doubly Linked List
Solve this ProblemHard30–35 min
Topics
Linked ListDoubly Linked ListRecursionDFS
Companies
Practice:GFG ↗AmazonMicrosoftGoogle
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.
Test Case 1:
Input:lists = [[4, 8, 3, 15], [7, 12], [9]], childOf = [[0, 1], [1, 0]]
Output:[4, 8, 7, 9, 12, 3, 15]
Explanation:The node holding 8 has a child list [7, 12], and within that child list, the node holding 7 has its own child [9] — two levels of nesting.
Test Case 2:
Input:lists = [[2, 5, 9]], childOf = []
Output:[2, 5, 9]
Explanation:No node has a child, so the list is already flat.
Test Case 3:
Input:lists = [[1, 3], [2]], childOf = [[0, 0]]
Output:[1, 2, 3]
Explanation:A single-level child spliced into the middle of its parent.
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
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — DFS Collect Every Value, Then Rebuild
GoodSince flattening always visits a node, then its entire child subtree (if any), then its own next node — a depth-first preorder walk — the simplest approach is to just record that visiting order into an array without touching any pointers, then build a brand new single-level list from the array afterward. Correct and easy to reason about, but it allocates an array (and a whole new chain of nodes) the size of the final flattened list.
Time
O(n)Space
O(n)Java
1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 static class MNode {
9 int val;
10 MNode next;
11 MNode prev;
12 MNode child;
13 MNode(int val) { this.val = val; }
14 }
15
16 private MNode buildChain(Node head) {
17 MNode dHead = null, dTail = null;
18 Node curr = head;
19 while (curr != null) {
20 MNode node = new MNode(curr.val);
21 if (dHead == null) {
22 dHead = node;
23 } else {
24 node.prev = dTail;
25 dTail.next = node;
26 }
27 dTail = node;
28 curr = curr.next;
29 }
30 return dHead;
31 }
32
33 private void collect(MNode head, List<Integer> out) {
34 MNode curr = head;
35 while (curr != null) {
36 out.add(curr.val);
37 if (curr.child != null) collect(curr.child, out);
38 curr = curr.next;
39 }
40 }
41
42 public Node flattenMultilevel(List<Node> lists, int[][] childOf) {
43 int n = lists.size();
44 MNode[] chains = new MNode[n];
45 for (int i = 0; i < n; i++) {
46 chains[i] = buildChain(lists.get(i));
47 }
48 for (int i = 0; i < childOf.length; i++) {
49 int parentIdx = childOf[i][0], pos = childOf[i][1];
50 MNode node = chains[parentIdx];
51 for (int k = 0; k < pos; k++) node = node.next;
52 node.child = chains[i + 1];
53 }
54 List<Integer> values = new ArrayList<>();
55 if (n > 0 && chains[0] != null) collect(chains[0], values);
56 Node dummy = new Node(0);
57 Node tail = dummy;
58 for (int v : values) {
59 tail.next = new Node(v);
60 tail = tail.next;
61 }
62 return dummy.next;
63 }
64}Optimal — Recursive DFS, Splice In Place
OptimalNo copy is needed at all. Recursively flatten a node's child list first (which itself may have children — this is where the recursion pays off, since a nested child's child gets flattened before it's ever spliced anywhere). Then splice that already-flat child chain directly between the node and whatever originally came after it, and continue walking from there. Each node is visited once, and every splice reuses the node objects that already exist — no rebuilding.
Time
O(n)Space
O(1) extraJava
1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 static class MNode {
9 int val;
10 MNode next;
11 MNode prev;
12 MNode child;
13 MNode(int val) { this.val = val; }
14 }
15
16 private MNode buildChain(Node head) {
17 MNode dHead = null, dTail = null;
18 Node curr = head;
19 while (curr != null) {
20 MNode node = new MNode(curr.val);
21 if (dHead == null) {
22 dHead = node;
23 } else {
24 node.prev = dTail;
25 dTail.next = node;
26 }
27 dTail = node;
28 curr = curr.next;
29 }
30 return dHead;
31 }
32
33 private MNode flatten(MNode head) {
34 MNode curr = head;
35 MNode tail = head;
36 while (curr != null) {
37 MNode next = curr.next;
38 if (curr.child != null) {
39 MNode childTail = flatten(curr.child);
40 curr.next = curr.child;
41 curr.child.prev = curr;
42 curr.child = null;
43 childTail.next = next;
44 if (next != null) next.prev = childTail;
45 tail = childTail;
46 } else {
47 tail = curr;
48 }
49 curr = next;
50 }
51 return tail;
52 }
53
54 public Node flattenMultilevel(List<Node> lists, int[][] childOf) {
55 int n = lists.size();
56 MNode[] chains = new MNode[n];
57 for (int i = 0; i < n; i++) {
58 chains[i] = buildChain(lists.get(i));
59 }
60 for (int i = 0; i < childOf.length; i++) {
61 int parentIdx = childOf[i][0], pos = childOf[i][1];
62 MNode node = chains[parentIdx];
63 for (int k = 0; k < pos; k++) node = node.next;
64 node.child = chains[i + 1];
65 }
66 if (n == 0 || chains[0] == null) return null;
67 flatten(chains[0]);
68 Node dummy = new Node(0);
69 Node tail = dummy;
70 MNode c = chains[0];
71 while (c != null) {
72 tail.next = new Node(c.val);
73 tail = tail.next;
74 c = c.next;
75 }
76 return dummy.next;
77 }
78}