Flattening Multilevel & Nested Lists

July 2026 · 19 min read

"Flattening" is one algorithm wearing four costumes. Whether the structure is a doubly linked list with child branches, a grid of sorted bottom columns, a binary tree, or arbitrarily nested integers, the job is identical: walk a branching structure in a fixed order and rewire it into a single linear chain. Learn the depth-first splice once and all four collapse into the same move.

Flatten a Multilevel Doubly Linked List (LC 430)

Each node has three pointers — prev, next, and a child that heads its own multilevel list:

class Node {
public:
    int   val;
    Node* prev;
    Node* next;
    Node* child;
};

You must produce a flat doubly linked list, depth-first: whenever a node has a child, the entire child list appears immediately after that node and before its original next. The DFS insight is a splice. When you reach a node cur with a child, you cut the list open between cur and cur->next, drop the whole (already flattened) child list into the gap, and continue. Because the list is doubly linked, that splice touches four pointers, and you must also null the child field so the output is genuinely single-level:

1. cur->next = childHead and childHead->prev = cur — attach the child after cur.
2. childTail->next = oldNext and (if it exists) oldNext->prev = childTail — reconnect the tail.
3. cur->child = nullptr — the field is now meaningless and must be cleared.

Depth-first is not a stylistic preference here; it is the specification. The required output reads as though you fully expanded every node's child before advancing to its next — precisely a preorder walk of the tree whose edges are next and child. A breadth-first pass would interleave a node's siblings with its descendants and produce the wrong order, so every correct solution is really just preorder DFS with the “visit” step replaced by a four-pointer splice.

The explicit-stack iterative version

A stack turns the recursion inside out. Push a node's next first, then its child, so the child is popped and processed first — that is the depth-first order:

Node* flatten(Node* head) {
    if (!head) return nullptr;
    std::stack<Node*> st;
    st.push(head);
    Node* prev = nullptr;

    while (!st.empty()) {
        Node* cur = st.top(); st.pop();
        if (prev) { prev->next = cur; cur->prev = prev; }

        if (cur->next)  st.push(cur->next);      // pushed first  -> resumed later
        if (cur->child) {
            st.push(cur->child);                 // pushed last   -> descended first
            cur->child = nullptr;                // REQUIRED: clear the child link
        }
        prev = cur;
    }
    return head;
}

Watch the space cost: the explicit stack can hold O(n) frames in the worst case — a list in which every node carries a child degenerates into pushing one saved next per node before any of them is popped. The recursive form instead costs O(depth) stack, strictly smaller whenever the nesting is shallower than the list is long. Neither dominates universally, which is why the two “430” rows in the complexity table are genuinely different trade-offs rather than the same bound written twice.

The recursive version that returns the tail

The recursive form is cleaner, but the design decision that makes it O(n) is subtle: the helper returns the tail of the sublist it flattened. Without the tail you would have to re-walk each flattened child to find where to reattach the parent's next — and re-walking at every level turns the cost into O(n · depth). Returning the tail makes each reattachment O(1), so the whole thing is a single O(n) sweep:

// flattens the level starting at `node`, returns its last node
Node* flattenTail(Node* node) {
    Node* cur  = node;
    Node* last = nullptr;
    while (cur) {
        Node* next = cur->next;
        if (cur->child) {
            Node* childTail = flattenTail(cur->child);
            cur->next         = cur->child;      // 1: attach child after cur
            cur->child->prev  = cur;
            cur->child        = nullptr;         // 3: clear the field
            childTail->next   = next;            // 2: reconnect the tail
            if (next) next->prev = childTail;
            last = childTail;
        } else {
            last = cur;
        }
        cur = next;                             // continue on the ORIGINAL next
    }
    return last;
}

Node* flatten(Node* head) { flattenTail(head); return head; }

The line cur = next uses the saved original next, not cur->next (which now points into the child). Miss that and you re-descend into the child you just spliced.

A three-level dry run

Take the canonical shape (children shown indented):

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

Depth-first, flattenTail descends at 3 into 7…10, descends again at 8 into 11–12, and returns tails bottom-up: the 11–12 level returns 12, spliced after 8; the 7–10 level returns 10, spliced after 3; the top level reattaches 4 after 10. Result:

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

Every child is now nullptr and every prev points at the physically preceding node — both invariants matter (see the pitfall below).

Flatten next/bottom Columns of Sorted Lists

A different shape: each node has next (to the next column head) and bottom (down its own sorted list). Flatten everything into one sorted bottom-linked list. Because every column is already sorted, this is a k-way merge. The compact recursive form flattens the columns to the right first, then merges the current column into that accumulated sorted list — a right-to-left fold:

Node* merge(Node* a, Node* b) {
    if (!a) return b;
    if (!b) return a;
    Node* head;
    if (a->val <= b->val) { head = a; head->bottom = merge(a->bottom, b); }
    else                  { head = b; head->bottom = merge(a, b->bottom); }
    head->next = nullptr;
    return head;
}

Node* flatten(Node* root) {
    if (!root || !root->next) return root;
    root->next = flatten(root->next);   // flatten the suffix first
    return merge(root, root->next);     // fold current column into it
}

With k columns and N total nodes this is O(N · k) in the worst case, because each merge re-walks the growing accumulator. When k is large, switch to an explicit min-heap of the current column heads: pop the smallest, append it, push its bottom. That is a genuine k-way merge in O(N log k) time and O(k) heap space — the same upgrade you would make for "merge k sorted lists."

The decision mirrors merge k sorted lists exactly. For a handful of columns the right-to-left fold is simpler to write and its worse asymptotics never bite; once k grows, the repeated re-walking of the accumulator dominates and the heap's O(N log k) wins decisively. Reach for the heap only when k is genuinely large or profiling fingers the fold as the bottleneck — otherwise the extra heap machinery is complexity you are paying for and not using.

Flatten a Binary Tree to a Linked List (LC 114)

Same idea, tree edition: rewire a binary tree into a right-leaning chain in preorder, using the right pointer as next and leaving left null. The O(1)-space method is Morris-like — for each node with a left subtree, find that subtree's rightmost node, hang the current right subtree off it, then swing the left subtree over to the right:

void flatten(TreeNode* root) {
    TreeNode* cur = root;
    while (cur) {
        if (cur->left) {
            TreeNode* pre = cur->left;
            while (pre->right) pre = pre->right;   // rightmost of left subtree
            pre->right = cur->right;               // thread current right onto it
            cur->right = cur->left;                // left subtree becomes the chain
            cur->left  = nullptr;
        }
        cur = cur->right;
    }
}

The recursive alternative flattens in reverse preorder (right, then left, then root), keeping a running prev and pointing each node's right at the previously visited node:

TreeNode* prev = nullptr;
void flatten(TreeNode* root) {
    if (!root) return;
    flatten(root->right);
    flatten(root->left);
    root->right = prev;      // stitch onto the already-built suffix
    root->left  = nullptr;
    prev = root;
}

Both share the exact idea behind the DLL splice: rewire pointers so the branching structure becomes a chain. Only the traversal order and the pointer names differ.

Nulling left at every node is not cosmetic. The problem defines the output as a list that walks purely through right; a leftover left pointer both fails the judge and silently turns a later traversal back into a tree walk. It is the tree analogue of clearing child in the multilevel list — the same class of bug (a stale branch pointer) that passes tiny hand-built tests and detonates on the large ones.

Nested Integers: The General Case (LC 339, 341)

Push nesting to its limit and you get a NestedInteger that is either a single integer or a list of NestedIntegers, to any depth. Weighted sum (LC 339) is a plain DFS that carries the depth as a multiplier:

int dfs(const std::vector<NestedInteger>& list, int depth) {
    int sum = 0;
    for (const auto& ni : list) {
        if (ni.isInteger()) sum += ni.getInteger() * depth;
        else                sum += dfs(ni.getList(), depth + 1);
    }
    return sum;
}

The Nested Iterator (LC 341) is the streaming version, and its key property is laziness: it does not flatten everything up front. A stack holds pending items (children pushed reversed, so the top is the next element); hasNext unwraps lists only when it needs to expose the next integer:

class NestedIterator {
    std::stack<NestedInteger> st;
    void pushReversed(const std::vector<NestedInteger>& v) {
        for (int i = (int)v.size() - 1; i >= 0; --i) st.push(v[i]);
    }
public:
    NestedIterator(std::vector<NestedInteger>& nestedList) { pushReversed(nestedList); }

    bool hasNext() {
        while (!st.empty() && !st.top().isInteger()) {
            NestedInteger ni = st.top(); st.pop();
            pushReversed(ni.getList());        // expand one level, lazily
        }
        return !st.empty();
    }
    int next() { int v = st.top().getInteger(); st.pop(); return v; }
};

Both nested problems are the same DFS routed to a different output channel: the weighted sum accumulates as it descends, while the iterator suspends the descent on a stack so each next is amortised O(1). Laziness earns its keep when the structure is huge or the consumer stops early — you never pay to flatten branches you never visit, which is exactly the property a database cursor or a streaming JSON reader needs.

Complexity at a Glance

Check Yourself

Six situations across the flattening family. Pick the statement that is actually true.

Practice

• LeetCode 430 — Flatten a Multilevel Doubly Linked List core do it iteratively and recursively; assert every child is null afterwards.
• LeetCode 114 — Flatten Binary Tree to Linked List tree get the Morris-like O(1) version working.
• LeetCode 341 — Flatten Nested List Iterator lazy keep it lazy: do not flatten in the constructor.
• LeetCode 339 — Nested List Weight Sum depth DFS carrying the depth multiplier.
• LeetCode 23 — Merge k Sorted Lists k-way the min-heap that upgrades the next/bottom merge.
• LeetCode 426 — Convert BST to Sorted Doubly Linked List inorder the same rewire-into-a-chain move, in sorted order.