Flatten a Multilevel Doubly Linked List

MediumLinked List · DFS · In-place Splicing🧩 Linked List Techniques LeetCode #430 ↗Updated Oct 30, 2026

Problem

Each node of a doubly linked list has prev, next and an extra child pointer that may lead to another doubly linked list, which can have children of its own. Flatten the structure into one level: a node's child list must appear right after that node and before its old next. Set every child to null, keep prev links correct, and return the head.

Input[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]

Input[1,2,null,3]Output[1,3,2]

Input[]Output[]

0 ≤ number of nodes ≤ 1000 · 1 ≤ Node.val ≤ 10⁵

Try it yourself

Java

class Solution {
    public Node flatten(Node head) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The flattened order is exactly a pre-order DFS (node, then its child list, then its next). It can be done without any stack: when a node has a child, find the child list's tail and splice the whole child list between the node and its next, then keep walking — deeper children get handled when the walk reaches them.

PatternLinked List Techniques

Instinct Nodes joined by next pointers and the task is to reverse, splice, merge, reorder or remove in place - grab a dummy head and rewire pointers carefully.

Memory hack Save next, flip, step - never let go of a rope before you've grabbed the next one.

Open the Linked List Techniques guide →

Approaches

Brute ForceCollect in DFS Order, Relink Everything

Time O(n)Space O(n)

Do a pre-order walk (node → child list → rest) and append each node to an ArrayList; reading all pointers first means nothing is lost. Then rewrite prev/next from the array and clear every child.

Java

public Node flatten(Node head) {
    List<Node> order = new ArrayList<>();
    collect(head, order);
    for (int i = 0; i < order.size(); i++) {
        Node n = order.get(i);
        n.child = null;
        n.prev = i > 0 ? order.get(i - 1) : null;
        n.next = i + 1 < order.size() ? order.get(i + 1) : null;
    }
    return head;
}

private void collect(Node node, List<Node> order) {
    for (Node c = node; c != null; c = c.next) {
        order.add(c);
        if (c.child != null) collect(c.child, order);
    }
}

Very hard to get wrong, but stores every node a second time.

BetterRecursive DFS Returning the Tail

Time O(n)Space O(depth)

A helper flattens one level and returns its last node. When it meets a node with a child, it recursively flattens the child, which hands back the child's tail, so the child list can be wired in between the node and its saved next in O(1).

Java

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

// flattens the list starting at node and returns its last node
private Node flattenTail(Node node) {
    Node last = null;
    while (node != null) {
        Node next = node.next;
        if (node.child != null) {
            Node childTail = flattenTail(node.child);
            node.next = node.child;
            node.child.prev = node;
            node.child = null;
            childTail.next = next;
            if (next != null) next.prev = childTail;
            last = childTail;
        } else {
            last = node;
        }
        node = next;
    }
    return last;
}

Relinks in place with no node array; recursion depth equals nesting depth.

OptimalIterative Splice (No Stack)

Time O(n)Space O(1)

Walk with cur. On a child, walk the child level to its tail, link tail ↔ cur.next and cur ↔ child, clear the child, and continue from cur.next (now the child's head). Each level is tail-searched once before it is spliced, so total work stays linear.

Java

public Node flatten(Node head) {
    for (Node cur = head; cur != null; cur = cur.next) {
        if (cur.child == null) continue;
        Node tail = cur.child;
        while (tail.next != null) tail = tail.next; // end of the child level
        tail.next = cur.next;
        if (cur.next != null) cur.next.prev = tail;
        cur.next = cur.child;
        cur.child.prev = cur;
        cur.child = null;
    }
    return head;
}

Linear time, constant extra memory — no recursion, no stack.

Pro tip

Explain why it is still O(n): a level's tail is searched only once, right before that level is merged into its parent.

At a glance

Level	Approach	Time	Space
Brute Force	Collect in DFS Order, Relink Everything	`O(n)`	`O(n)`
Better	Recursive DFS Returning the Tail	`O(n)`	`O(depth)`
Optimal	Iterative Splice (No Stack)	`O(n)`	`O(1)`

Common pitfalls

Forgetting child = null — the judge rejects a list that still has children.
Fixing next but not prev (both for the child head and the old next).
Losing the old next before splicing — save it first.

Interview tips

Rotate the picture 45°: it is a binary tree (child = left, next = right) and the answer is pre-order.
Mention the explicit-stack variant (push next, then child) as another O(n) option.
Test a child on the last node and a child-of-child chain.

Pattern

Pre-order flatten by splicing → turn nested / branching links into one list in place.

My notes saved in this browser