Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Flatten a Multilevel Doubly Linked List

HARDProblemSolveExternal Links

Description

You are given a doubly linked list where each node has three pointers: next (pointing to the next node), prev (pointing to the previous node), and an additional child pointer. The child pointer may or may not point to a separate doubly linked list. These child lists may themselves have children, forming a multilevel structure.

Given the head of the first level of the list, flatten the entire structure into a single-level doubly linked list.

The rule for flattening is: if a node has a child list, the nodes from that child list should appear immediately after the current node and before the current node's next node. After flattening, all child pointers must be set to null.

Think of it like reading a document with footnotes. When you encounter a footnote reference, you read the entire footnote (and any sub-footnotes) before continuing with the main text. The child list is the footnote — it gets inserted right where you found it.

Examples

Example 1

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: The multilevel structure is:

Level 1: 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5 ↔ 6

Level 2 (child of 3): 7 ↔ 8 ↔ 9 ↔ 10

Level 3 (child of 8): 11 ↔ 12

Flattening inserts the child of 3 (the list starting at 7) right after 3 and before 4. Within that child list, node 8 also has a child (starting at 11), which gets inserted after 8 and before 9. The final flat list is: 1 ↔ 2 ↔ 3 ↔ 7 ↔ 8 ↔ 11 ↔ 12 ↔ 9 ↔ 10 ↔ 4 ↔ 5 ↔ 6.

Example 2

Input: head = [1, 2, null, 3]

Output: [1, 3, 2]

Explanation: The structure is: 1 ↔ 2 (level 1), and node 1 has a child pointing to 3 (level 2). Flattening inserts 3 right after 1 and before 2, giving: 1 ↔ 3 ↔ 2.

Example 3

Input: head = []

Output: []

Explanation: An empty list remains empty.

Constraints

  • The number of nodes will not exceed 1000
  • 1 ≤ Node.val ≤ 10^5

Editorial

Using Stack (DFS Order)

Intuition

Flattening a multilevel list is essentially a depth-first traversal. Whenever we encounter a node with a child, we dive into the child list first before continuing with the next node. This is exactly the behavior of a stack (Last-In, First-Out).

The idea is simple:

  1. Push the head node onto a stack.
  2. Pop a node, and for that node:
    • If it has a next pointer, push the next node onto the stack.
    • If it has a child pointer, push the child node onto the stack.
  3. Since the stack is LIFO, the child (pushed last) will be popped first — this ensures child nodes are processed before next nodes, which is exactly the flattening order we need.
  4. Link each popped node to the previously popped node with proper prev/next pointers.
  5. Set the child pointer to null.

Important detail: we must push next before child onto the stack. That way, child ends up on top and gets processed first, while next waits below and gets processed after the entire child subtree is done.

Think of it like a browser's back stack. When you click a link (child), the current page (next) is saved on the stack. After you finish reading all linked pages, you come back to where you left off.

Step-by-Step Explanation

Let's trace through a simpler example: 1 ↔ 2 ↔ 3, where node 2 has a child list 4 ↔ 5.

Expected output: 1 ↔ 2 ↔ 4 ↔ 5 ↔ 3

Step 1: Push head node(1) onto the stack. Stack: [1]. prev = null.

Step 2: Pop node(1). It has next = node(2), push it. No child. Stack: [2]. Link: nothing (prev was null). Set prev = node(1). Building: 1.

Step 3: Pop node(2). It has next = node(3) — push it. It has child = node(4) — push it on top. Stack: [3, 4]. Link prev(1) → node(2), node(2).prev = node(1). Set prev = node(2). Building: 1 ↔ 2.

Step 4: Pop node(4) — the child! (It was on top because we pushed it after next.) It has next = node(5) — push it. No child. Stack: [3, 5]. Link prev(2) → node(4), node(4).prev = node(2). Set child = null. Set prev = node(4). Building: 1 ↔ 2 ↔ 4.

Step 5: Pop node(5). No next, no child. Stack: [3]. Link prev(4) → node(5), node(5).prev = node(4). Set prev = node(5). Building: 1 ↔ 2 ↔ 4 ↔ 5.

Step 6: Pop node(3). No next, no child. Stack: []. Link prev(5) → node(3), node(3).prev = node(5). Set prev = node(3). Building: 1 ↔ 2 ↔ 4 ↔ 5 ↔ 3.

Step 7: Stack empty. Done! Result: [1, 2, 4, 5, 3].

Stack-Based DFS Flattening — Watch how we use a stack to process child lists before continuing with next pointers, building the flattened list node by node.

Algorithm

  1. If head is null, return null.
  2. Initialize a stack and push the head node.
  3. Initialize prev = null.
  4. While the stack is not empty:
    a. Pop the top node as curr.
    b. If curr.next exists, push curr.next onto the stack.
    c. If curr.child exists, push curr.child onto the stack.
    d. If prev is not null, set prev.next = curr and curr.prev = prev.
    e. Set curr.child = null.
    f. Set prev = curr.
  5. Return head.

Code

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
};
*/

class Solution {
public:
    Node* flatten(Node* head) {
        if (!head) return nullptr;
        
        stack<Node*> stk;
        stk.push(head);
        Node* prev = nullptr;
        
        while (!stk.empty()) {
            Node* curr = stk.top();
            stk.pop();
            
            // Push next first (processed later), then child (processed sooner)
            if (curr->next) stk.push(curr->next);
            if (curr->child) stk.push(curr->child);
            
            if (prev) {
                prev->next = curr;
                curr->prev = prev;
            }
            curr->child = nullptr;
            prev = curr;
        }
        
        return head;
    }
};
"""
# Definition for a Node.
class Node:
    def __init__(self, val, prev, next, child):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child
"""

class Solution:
    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None
        
        stack = [head]
        prev = None
        
        while stack:
            curr = stack.pop()
            
            # Push next first (processed later), then child (processed sooner)
            if curr.next:
                stack.append(curr.next)
            if curr.child:
                stack.append(curr.child)
            
            if prev:
                prev.next = curr
                curr.prev = prev
            curr.child = None
            prev = curr
        
        return head
/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};
*/

class Solution {
    public Node flatten(Node head) {
        if (head == null) return null;
        
        Deque<Node> stack = new ArrayDeque<>();
        stack.push(head);
        Node prev = null;
        
        while (!stack.isEmpty()) {
            Node curr = stack.pop();
            
            // Push next first (processed later), then child (processed sooner)
            if (curr.next != null) stack.push(curr.next);
            if (curr.child != null) stack.push(curr.child);
            
            if (prev != null) {
                prev.next = curr;
                curr.prev = prev;
            }
            curr.child = null;
            prev = curr;
        }
        
        return head;
    }
}

Complexity Analysis

Time Complexity: O(n)

Every node is pushed onto the stack exactly once and popped exactly once. Each push/pop operation is O(1). The total work is proportional to the number of nodes n.

Space Complexity: O(n)

In the worst case, the stack holds O(n) nodes. For example, if the list is a single chain of nodes each with a child that has a next pointer, the stack could grow to hold roughly n/2 nodes simultaneously. The stack uses O(n) extra space.

Why This Approach Is Not Efficient

The stack-based approach correctly flattens the list in O(n) time, which is optimal — we must visit every node at least once. However, it uses O(n) extra space for the stack, and this is unnecessary.

The core inefficiency is that we use the stack to remember where to resume after processing a child list. But we don't need external storage for this. The information about what comes after the child list is already encoded in the list itself — it's just the current node's next pointer.

Instead of saving next pointers on a stack, we can splice the child list directly into the main list, in-place. When we encounter a node with a child:

  1. Find the tail of the child list.
  2. Connect the tail to the current node's next.
  3. Make the child the current node's new next.
  4. Clear the child pointer.

This way, the child list becomes part of the main list, and we simply continue iterating forward. No stack needed — just pointer manipulation. This eliminates the O(n) extra space entirely.

Optimal Approach - In-Place Iterative Flattening

Intuition

Instead of using a stack to track where to come back to, we can flatten the list in-place by splicing child lists directly into the main list as we encounter them.

The key insight is: when we find a node with a child, the child list should go between the current node and its next node. So we:

  1. Find the tail (last node) of the child list.
  2. Connect the tail's next to the current node's next (the node that should come after the entire child subtree).
  3. Make the child the current node's next (inserting the child list right after current).
  4. Clear the child pointer.
  5. Continue iterating forward.

After the splice, the child list's nodes are now part of the main list. When we continue iterating, we'll naturally walk through the child list's nodes. If any of those nodes also have children, we'll handle them the same way — splice their children into the main list and keep going.

This is like unfolding a nested outline: whenever you see a sub-list, you inline it right where it is. You only walk forward, and each splice operation brings nested content up to the current level. All nodes end up in the correct DFS order without any extra data structures.

The time complexity is still O(n) because each node is visited at most twice: once during the main forward traversal, and at most once during a tail-finding operation. Once a child list is spliced in, its nodes join the main list and are not traversed again for tail-finding.

Step-by-Step Explanation

Let's trace through the main example:

Level 1: 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5 ↔ 6

Level 2 (child of 3): 7 ↔ 8 ↔ 9 ↔ 10

Level 3 (child of 8): 11 ↔ 12

Step 1: Start at curr = node(1). No child. Move to node(2). No child. Move to node(3).

Step 2: curr = node(3) has a child = node(7)! Find the tail of child list: traverse 7 → 8 → 9 → 10. Tail = node(10).

Step 3: Splice the child list:

  • Set node(10).next = node(4), node(4).prev = node(10) — connect tail to original next.
  • Set node(3).next = node(7), node(7).prev = node(3) — make child the new next.
  • Set node(3).child = null.
  • List is now: 1 ↔ 2 ↔ 3 ↔ 7 ↔ 8 ↔ 9 ↔ 10 ↔ 4 ↔ 5 ↔ 6 (with node 8 still having a child).

Step 4: Move to curr.next = node(7). No child. Move to node(8).

Step 5: curr = node(8) has a child = node(11)! Find the tail of child list: 11 → 12. Tail = node(12).

Step 6: Splice the child list:

  • Set node(12).next = node(9), node(9).prev = node(12).
  • Set node(8).next = node(11), node(11).prev = node(8).
  • Set node(8).child = null.
  • List is now: 1 ↔ 2 ↔ 3 ↔ 7 ↔ 8 ↔ 11 ↔ 12 ↔ 9 ↔ 10 ↔ 4 ↔ 5 ↔ 6.

Step 7: Continue forward: nodes 11, 12, 9, 10, 4, 5, 6 — none have children. Reach end.

Result: [1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6].

In-Place Iterative Flattening — Splice Child Lists on the Fly — Watch how we traverse the list and splice each child list directly into the main chain. When node 3's child is spliced, and then node 8's child is spliced, the entire multilevel structure becomes a single flat list — all without extra space.

Algorithm

  1. Initialize curr = head.
  2. While curr is not null:
    a. If curr has a child:
    • Save child = curr.child.
    • Find the tail of the child list: start at child, walk .next until the end.
    • Connect tail to curr.next: set tail.next = curr.next. If curr.next exists, set curr.next.prev = tail.
    • Connect curr to child: set curr.next = child, child.prev = curr.
    • Clear the child pointer: set curr.child = null.
      b. Move forward: set curr = curr.next.
  3. Return head.

Code

class Solution {
public:
    Node* flatten(Node* head) {
        Node* curr = head;
        
        while (curr) {
            if (curr->child) {
                Node* child = curr->child;
                
                // Find the tail of the child list
                Node* tail = child;
                while (tail->next) {
                    tail = tail->next;
                }
                
                // Connect tail to curr->next
                tail->next = curr->next;
                if (curr->next) {
                    curr->next->prev = tail;
                }
                
                // Connect curr to child
                curr->next = child;
                child->prev = curr;
                curr->child = nullptr;
            }
            curr = curr->next;
        }
        
        return head;
    }
};
class Solution:
    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':
        curr = head
        
        while curr:
            if curr.child:
                child = curr.child
                
                # Find the tail of the child list
                tail = child
                while tail.next:
                    tail = tail.next
                
                # Connect tail to curr.next
                tail.next = curr.next
                if curr.next:
                    curr.next.prev = tail
                
                # Connect curr to child
                curr.next = child
                child.prev = curr
                curr.child = None
            
            curr = curr.next
        
        return head
class Solution {
    public Node flatten(Node head) {
        Node curr = head;
        
        while (curr != null) {
            if (curr.child != null) {
                Node child = curr.child;
                
                // Find the tail of the child list
                Node tail = child;
                while (tail.next != null) {
                    tail = tail.next;
                }
                
                // Connect tail to curr.next
                tail.next = curr.next;
                if (curr.next != null) {
                    curr.next.prev = tail;
                }
                
                // Connect curr to child
                curr.next = child;
                child.prev = curr;
                curr.child = null;
            }
            curr = curr.next;
        }
        
        return head;
    }
}

Complexity Analysis

Time Complexity: O(n)

Each node is visited at most twice in total: once during the main forward traversal (the while loop over curr), and at most once during a tail-finding traversal. Once a child list is spliced into the main list, its nodes become part of the main chain and will not be traversed again during any future tail-finding. Therefore the total work across all tail-finding operations plus the main traversal is O(n).

Space Complexity: O(1)

We use only a constant number of pointer variables: curr, child, and tail. No stack, no recursion, no auxiliary data structures. The flattening is done entirely in-place by rearranging the existing pointers.