LeetCode #430 Hard

Flatten a Multilevel Doubly Linked List

Nodes have next, prev and a possible child sublist (itself multilevel). Flatten into one level, children spliced in right after their parent.

linked-listdfsstack

Open on LeetCode ↗

02

Intuition

💡

Depth-first order is exactly the flattened order: node, then its child list, then its former next. A stack remembers the interrupted next while we dive into a child — pop it back when the child branch is exhausted.

03

Approach

1

Walk with a stack

At each node: if it has a child, push its next (may be null-skipped) and rewire next to the child. The child pointer is cleared.

2

Resume on dead ends

When next is null and the stack isn't empty, pop the saved node and splice it after the current node, fixing both directions.

3

Keep prev consistent

Every rewire sets next.prev too — the doubly-linked invariant is maintained throughout.

04

Solution & live demo

python

▶1class Solution:
▶2    def flatten(self, head):
▶3        cur, stack = head, []
▶4        while cur:
▶5            if cur.child:
▶6                if cur.next: stack.append(cur.next)
▶7                cur.next = cur.child
▶8                cur.child.prev = cur
▶9                cur.child = None
▶10            elif not cur.next and stack:
▶11                nxt = stack.pop()
▶12                cur.next = nxt
▶13                nxt.prev = cur
▶14            cur = cur.next
▶15        return head

05

Edge cases

child on the last node of a level

Nothing to push; the child simply continues the list.

Empty head

Return null immediately.

06

Complexity

Time

O(n)

Space

O(d)

Each node visited once; stack depth = nesting depth.