LeetCode #430 — MEDIUM

Flatten a Multilevel Doubly Linked List

Move from brute-force thinking to an efficient approach using linked list strategy.

The Problem

Problem Statement

You are given a doubly linked list, which contains nodes that have a next pointer, a previous 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 as shown in the example below.

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:

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 linked list in the input is shown.
After flattening the multilevel linked list it becomes:

Example 2:

Input: head = [1,2,null,3]
Output: [1,3,2]
Explanation: The multilevel linked list in the input is shown.
After flattening the multilevel linked list it becomes:

Example 3:

Input: head = []
Output: []
Explanation: There could be empty list in the input.

Constraints:

The number of Nodes will not exceed 1000.
1 <= Node.val <= 10⁵

How the multilevel linked list is represented in test cases:

We use the multilevel linked list from Example 1 above:

 1---2---3---4---5---6--NULL
         |
         7---8---9---10--NULL
             |
             11--12--NULL

The serialization of each level is as follows:

[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]

To serialize all levels together, we will add nulls in each level to signify no node connects to the upper node of the previous level. The serialization becomes:

[1,    2,    3, 4, 5, 6, null]
             |
[null, null, 7,    8, 9, 10, null]
                   |
[            null, 11, 12, null]

Merging the serialization of each level and removing trailing nulls we obtain:

[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

Step 01

Brute Force Baseline

Problem summary: You are given a doubly linked list, which contains nodes that have a next pointer, a previous 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 as shown in the example below. 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.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Linked List

Example 1

[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

Example 2

[1,2,null,3]

Example 3

[]

Core Insight

What unlocks the optimal approach

No official hints in dataset. Start from constraints and look for a monotonic or reusable state.

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Upper-end input sizes

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #430: Flatten a Multilevel Doubly Linked List
/*
// 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;
        }
        Node dummy = new Node();
        dummy.next = head;
        preorder(dummy, head);
        dummy.next.prev = null;
        return dummy.next;
    }

    private Node preorder(Node pre, Node cur) {
        if (cur == null) {
            return pre;
        }
        cur.prev = pre;
        pre.next = cur;

        Node t = cur.next;
        Node tail = preorder(cur, cur.child);
        cur.child = null;
        return preorder(tail, t);
    }
}

// Accepted solution for LeetCode #430: Flatten a Multilevel Doubly Linked List
// Auto-generated Go example from java.
func exampleSolution() {
}
// Reference (java):
// // Accepted solution for LeetCode #430: Flatten a Multilevel Doubly Linked List
// /*
// // 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;
//         }
//         Node dummy = new Node();
//         dummy.next = head;
//         preorder(dummy, head);
//         dummy.next.prev = null;
//         return dummy.next;
//     }
// 
//     private Node preorder(Node pre, Node cur) {
//         if (cur == null) {
//             return pre;
//         }
//         cur.prev = pre;
//         pre.next = cur;
// 
//         Node t = cur.next;
//         Node tail = preorder(cur, cur.child);
//         cur.child = null;
//         return preorder(tail, t);
//     }
// }

# Accepted solution for LeetCode #430: Flatten a Multilevel Doubly Linked List
"""
# 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: 'Node') -> 'Node':
        def preorder(pre, cur):
            if cur is None:
                return pre
            cur.prev = pre
            pre.next = cur

            t = cur.next
            tail = preorder(cur, cur.child)
            cur.child = None
            return preorder(tail, t)

        if head is None:
            return None
        dummy = Node(0, None, head, None)
        preorder(dummy, head)
        dummy.next.prev = None
        return dummy.next

// Accepted solution for LeetCode #430: Flatten a Multilevel Doubly Linked List
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
    pub fn rust_example() {
        // Port the logic from the reference block below.
    }
}

// Reference (java):
// // Accepted solution for LeetCode #430: Flatten a Multilevel Doubly Linked List
// /*
// // 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;
//         }
//         Node dummy = new Node();
//         dummy.next = head;
//         preorder(dummy, head);
//         dummy.next.prev = null;
//         return dummy.next;
//     }
// 
//     private Node preorder(Node pre, Node cur) {
//         if (cur == null) {
//             return pre;
//         }
//         cur.prev = pre;
//         pre.next = cur;
// 
//         Node t = cur.next;
//         Node tail = preorder(cur, cur.child);
//         cur.child = null;
//         return preorder(tail, t);
//     }
// }

// Accepted solution for LeetCode #430: Flatten a Multilevel Doubly Linked List
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #430: Flatten a Multilevel Doubly Linked List
// /*
// // 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;
//         }
//         Node dummy = new Node();
//         dummy.next = head;
//         preorder(dummy, head);
//         dummy.next.prev = null;
//         return dummy.next;
//     }
// 
//     private Node preorder(Node pre, Node cur) {
//         if (cur == null) {
//             return pre;
//         }
//         cur.prev = pre;
//         pre.next = cur;
// 
//         Node t = cur.next;
//         Node tail = preorder(cur, cur.child);
//         cur.child = null;
//         return preorder(tail, t);
//     }
// }

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(n)

Space

O(1)

Approach Breakdown

COPY TO ARRAY

O(n) time

O(n) space

Copy all n nodes into an array (O(n) time and space), then use array indexing for random access. Operations like reversal or middle-finding become trivial with indices, but the O(n) extra space defeats the purpose of using a linked list.

IN-PLACE POINTERS

O(n) time

O(1) space

Most linked list operations traverse the list once (O(n)) and re-wire pointers in-place (O(1) extra space). The brute force often copies nodes to an array to enable random access, costing O(n) space. In-place pointer manipulation eliminates that.

Shortcut: Traverse once + re-wire pointers → O(n) time, O(1) space. Dummy head nodes simplify edge cases.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Losing head/tail while rewiring

Wrong move: Pointer updates overwrite references before they are saved.

Usually fails on: List becomes disconnected mid-operation.

Fix: Store next pointers first and use a dummy head for safer joins.