Log inSign up
mediumLeetCodeNot Started

Flatten a Multilevel Doubly Linked List

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Linked List
Solve on LeetCode
Lesson

Problem Statement

You are given a doubly linked list, which contains nodes that have a next pointer, a prev pointer, and an additional child pointer. This child pointer may or may not point to a separate doubly linked list, also containing these special nodes. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure.

Given the head of the first level of the list, flatten the list so that all the nodes appear in a single-level, doubly linked list. Let curr be a node with a child list. The nodes in the child list should appear after curr and before curr.next in the flattened list.

Return the head of the flattened list. The nodes in the list must have all of their child pointers set to null.

Example 1 · Standard Multilevel List:

Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Output: [1,2,3,7,8,11,12,9,10,4,5,6]
Explanation: Node 3 has child 7. Node 8 has child 11. Flattening traverses 1->2->3, enters child 7->8, enters child 11->12, resumes 9->10, and finally resumes 4->5->6.

Example 2 · Single Child Branch:

Input: head = [1,2,null,3]
Output: [1,3,2]
Explanation: Node 1 has child 3 and next 2. Flattened result is 1 <-> 3 <-> 2.

Example 3 · Empty List:

Input: head = []
Output: []
Explanation: An empty list returns null.

Constraints:

  • The number of Nodes will not exceed 1000.
  • 1 <= Node.val <= 10^5
  • All nodes are valid doubly linked nodes with val, prev, next, and child pointers.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Map recursive tree traversal concepts onto hierarchical pointer structures.
  • Perform safe multi-node pointer surgery without losing list tails or corrupting prev links.
  • Achieve O(1) auxiliary space by splicing sublists into the main traversal stream.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Hierarchical/nested linked list branches requiring linear serialization.
  • Child branch must be fully processed before resuming current level's next node.
  • Doubly linked integrity (prev and next) must be preserved across level boundaries.

Algorithmic Decision Tree:

  • If allowed extra memory, an explicit stack holding curr.next whenever curr.child exists gives a clean iterative DFS.
  • If strict O(1) auxiliary space is required, splice the child segment directly into the current level by finding its tail and sewing pointers.

Connected Patterns:

Flatten Binary Tree to Linked ListPopulating Next Right Pointers in Each Node

1. Brute Force — Preorder DFS Collect into Vector & Rebuild

Intuition

Traverse the multilevel list recursively: visit the node, recursively visit its child branch, then recursively visit its next branch. Collect all visited nodes in order, then rewrite their prev, next, and child pointers.

Algorithm

  1. Step 1: Define a recursive helper dfs(node, list) that appends node, then calls dfs(node.child, list), then calls dfs(node.next, list).
  2. Step 2: Collect all nodes into an array nodes.
  3. Step 3: Iterate i from 0 to nodes.length - 1: set nodes[i].child = null, nodes[i].next = nodes[i+1] (if exists), and nodes[i+1].prev = nodes[i].
  4. Step 4: Return nodes[0].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Node {
7public:
8 int val;
9 Node* prev;
10 Node* next;
11 Node* child;
12 Node(int v) : val(v), prev(nullptr), next(nullptr), child(nullptr) {}
13};
14
15class Solution {
16 void dfs(Node* node, vector<Node*>& order) {
17 if (!node) return;
18 order.push_back(node);
19 dfs(node->child, order);
20 dfs(node->next, order);
21 }
22public:
23 Node* flatten(Node* head) {
24 if (!head) return nullptr;
25 vector<Node*> order;
26 dfs(head, order);
27 for (int i = 0; i < (int)order.size(); ++i) {
28 order[i]->child = nullptr;
29 order[i]->prev = (i > 0) ? order[i - 1] : nullptr;
30 order[i]->next = (i + 1 < (int)order.size()) ? order[i + 1] : nullptr;
31 }
32 return order[0];
33 }
34};
35
36int main() {
37 Node* n1 = new Node(1);
38 Node* n2 = new Node(2);
39 Node* n3 = new Node(3);
40 n1->next = n2; n2->prev = n1;
41 n1->child = n3;
42
43 Solution sol;
44 Node* flat = sol.flatten(n1);
45
46 cout << "Brute Force Flat: ";
47 for (Node* c = flat; c; c = c->next) {
48 cout << c->val << (c->next ? " <-> " : "");
49 }
50 cout << endl;
51 return 0;
52}

Time & Space Complexity

  • Time complexity: O(N) — Traverses all N nodes in preorder DFS to store them in a buffer, then performs a second pass of N iterations to rebuild links.
  • Space complexity: O(N) — Allocates a dynamic array/vector storing N node pointers.

Why Brute Force Doesn't Scale:

Array reconstruction uses O(N) auxiliary space which triggers garbage collection overhead on large datasets.

For 1,000,000 nodes, in-place splicing requires 0 bytes extra heap, while array collection allocates ~8MB memory.

2. Better — Iterative DFS with Explicit Stack

Intuition

Use an explicit stack. Push head to stack. At each step, pop curr, link it to prevNode (maintaining doubly linked links), push curr.next (if exists), push curr.child (if exists), and set curr.child = null.

Algorithm

  1. Step 1: If head is null, return null.
  2. Step 2: Initialize stack with head, and prev = null.
  3. Step 3: While stack is not empty: pop curr. If prev exists, set prev.next = curr and curr.prev = prev.
  4. Step 4: If curr.next exists, push curr.next onto stack.
  5. Step 5: If curr.child exists, push curr.child onto stack and set curr.child = null.
  6. Step 6: Update prev = curr.
  7. Step 7: Return head.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <stack>
3
4using namespace std;
5
6class Node {
7public:
8 int val;
9 Node* prev;
10 Node* next;
11 Node* child;
12 Node(int v) : val(v), prev(nullptr), next(nullptr), child(nullptr) {}
13};
14
15class Solution {
16public:
17 Node* flatten(Node* head) {
18 if (!head) return nullptr;
19 stack<Node*> st;
20 st.push(head);
21 Node* prev = nullptr;
22
23 while (!st.empty()) {
24 Node* curr = st.top();
25 st.pop();
26
27 if (prev) {
28 prev->next = curr;
29 curr->prev = prev;
30 }
31
32 if (curr->next) st.push(curr->next);
33 if (curr->child) {
34 st.push(curr->child);
35 curr->child = nullptr;
36 }
37
38 prev = curr;
39 }
40 return head;
41 }
42};
43
44int main() {
45 Node* n1 = new Node(1);
46 Node* n2 = new Node(2);
47 Node* n3 = new Node(3);
48 n1->next = n2; n2->prev = n1;
49 n1->child = n3;
50
51 Solution sol;
52 Node* flat = sol.flatten(n1);
53
54 cout << "Better Stack Flat: ";
55 for (Node* c = flat; c; c = c->next) {
56 cout << c->val << (c->next ? " <-> " : "");
57 }
58 cout << endl;
59 return 0;
60}

Time & Space Complexity

  • Time complexity: O(N) — Each node is pushed and popped from the stack at most once.
  • Space complexity: O(D) where D is maximum nesting depth — Stack holds suspended next pointers proportional to branch nesting depth (O(N) worst case, O(log N) balanced).

3. Optimal — In-Place Pointer Splicing (O(1) Auxiliary Space)

Intuition

Iterate pointer curr from head. If curr.child is non-null, find the tail of curr.child (childTail). Connect childTail.next = curr.next and curr.next.prev = childTail (if curr.next exists). Then set curr.next = curr.child, curr.child.prev = curr, and curr.child = null. Continue iterating curr = curr.next.

Algorithm

  1. Step 1: If head == null, return null.
  2. Step 2: Initialize curr = head.
  3. Step 3: While curr != null: if curr.child != null:
  4. a. Find tail of child list: childTail = curr.child; while childTail.next != null, advance childTail = childTail.next.
  5. b. Wire childTail.next = curr.next.
  6. c. If curr.next != null, wire curr.next.prev = childTail.
  7. d. Wire curr.next = curr.child and curr.child.prev = curr.
  8. e. Set curr.child = null.
  9. Step 4: Advance curr = curr.next.
  10. Step 5: Return head.

Multilevel Doubly Linked List Flattening Master Trace

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Advance from 3 to find tail node 4
Visual state
Values and pointers at this exact step
linked list
curr → 1child → 3
Node 1
1
Node 2
2
Node 3
3
Node 4
4
NULL
Check / comparison
curr.child != null
Decision / next transition
Find child tail
Why this step matters

Advance from 3 to find tail node 4.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5class Node {
6public:
7 int val;
8 Node* prev;
9 Node* next;
10 Node* child;
11 Node(int v) : val(v), prev(nullptr), next(nullptr), child(nullptr) {}
12};
13
14class Solution {
15public:
16 Node* flatten(Node* head) {
17 Node* curr = head;
18 while (curr) {
19 if (curr->child) {
20 Node* nextNode = curr->next;
21 Node* childTail = curr->child;
22 while (childTail->next) {
23 childTail = childTail->next;
24 }
25
26 // Connect childTail with nextNode
27 childTail->next = nextNode;
28 if (nextNode) nextNode->prev = childTail;
29
30 // Connect curr with curr->child
31 curr->next = curr->child;
32 curr->child->prev = curr;
33 curr->child = nullptr;
34 }
35 curr = curr->next;
36 }
37 return head;
38 }
39};
40
41int main() {
42 Node* n1 = new Node(1);
43 Node* n2 = new Node(2);
44 Node* n3 = new Node(3);
45 Node* n4 = new Node(4);
46 n1->next = n2; n2->prev = n1;
47 n1->child = n3;
48 n3->next = n4; n4->prev = n3;
49
50 Solution sol;
51 Node* flat = sol.flatten(n1);
52
53 cout << "Optimal In-Place Flat: ";
54 for (Node* c = flat; c; c = c->next) {
55 cout << c->val << (c->next ? " <-> " : "");
56 }
57 cout << endl;
58 return 0;
59}

Time & Space Complexity

  • Time complexity: O(N) — Each node is visited at most twice (once during iteration, once when finding child tail). Linear O(N) runtime.
  • Space complexity: O(1) — Mutates pointers strictly in-place with zero additional memory.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — DFS Preorder Collect & ReconstructO(N)O(N)Perform a standard recursive preorder traversal, collecting all nodes into an array/vector. Then iterate through the array to re-link all prev and next pointers and set child = null.Auxiliary array allocation.
2.Better — Iterative DFS with Explicit StackO(N)O(D) where D is max branch depthTraverse sequentially. When curr.child is non-null, push curr.next onto a stack, wire curr.next = curr.child, and clear curr.child. When hitting the end of a level, pop from the stack and connect to the tail.Stack memory for deep nested child hierarchies.
3.Optimal — In-Place Pointer Splicing (O(1) Auxiliary Space)OptimalO(N)O(1)Iterate curr from head. Whenever curr.child exists, find the tail of the child list. Connect childTail.next = curr.next, connect curr.next = curr.child, update both prev references, and set curr.child = null. Advance curr normally.Optimal.

Common Pitfalls & Crucial Edge Cases

Forgetting to update `prev` on `nextNode`

Setting childTail.next = nextNode without setting nextNode.prev = childTail breaks backward traversal.

Not setting `curr.child = null`

Failing to nullify child pointers violates problem specification.

Advancing `curr` to old `next` instead of new `next`

If you jump over the spliced child nodes, nested sub-children will not be flattened.

Crucial Edge Cases to Validate:

  • Empty List — head = null -> returns null.
  • No Child Pointers — Returns identical list with zero mutations.
  • Deeply Nested Chains — Nodes where every single node has a child and no next -> behaves like a singly linked list branch.
  • Child at Tail — When curr.next is null (e.g. child at last node of level), childTail.next correctly becomes null.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention the tree analogy immediately: 'This is identical to preorder traversal of a binary tree where child is left and next is right.'
  2. Explain why O(1) space is achievable by splicing without recursion.
  3. Always write a small 3-node diagram showing all 4 pointer re-assignments (curr.next, curr.child.prev, childTail.next, nextNode.prev).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What standard tree traversal order does multilevel linked list flattening correspond to?

2.Why does the in-place pointer splicing approach achieve O(N) time even though it scans to find child tails?

3.What happens if a node has a child list but its next pointer is null?

Back to DSA Sheet