LeetCode 430: Flatten a Multilevel Doubly Linked List

Problem Restatement

We are given the head of a multilevel doubly linked list.

Each node has four fields:

The child list can also contain nodes with their own child lists.

We need to flatten everything into one single-level doubly linked list.

When a node has a child list, that child list must appear immediately after the node and before the node’s original next node. After flattening, all child pointers must be None. The original nodes should be reused.

Input and Output

The node class is usually:

class Node:
    def __init__(self, val, prev=None, next=None, child=None):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child

Examples

Consider this structure:

1 - 2 - 3 - 4
    |
    5 - 6
        |
        7 - 8

The flattened list should be:

1 - 2 - 5 - 6 - 7 - 8 - 3 - 4

Why?

At node 2, the child list 5 - 6 must be inserted before node 3.

At node 6, the child list 7 - 8 must be inserted before returning to node 3.

All child pointers become None.

For an empty list:

head = None

the answer is:

None

First Thought: Collect Nodes

A simple approach is to do a depth-first traversal and store nodes in an array.

For example:

nodes = [1, 2, 5, 6, 7, 8, 3, 4]

Then we can reconnect them:

1 <-> 2 <-> 5 <-> 6 <-> 7 <-> 8 <-> 3 <-> 4

This works, but it uses extra storage for all nodes.

We can flatten the list directly by changing pointers as we traverse.

Key Insight

The flattening order is depth-first preorder.

For each node:

1. Visit the node itself.
2. If it has a child, flatten the child list next.
3. Then continue with the original next node.

The main pointer problem is this:

curr - next
 |
child

After flattening, we want:

curr - child_head - ... - child_tail - next

So when we see a child list, we need to:

1. Save curr.next.
2. Connect curr.next to curr.child.
3. Set curr.child.prev to curr.
4. Flatten the child list and find its tail.
5. Connect the child tail to the saved next node.
6. Set curr.child = None.

A recursive helper can return the tail of the flattened segment.

Algorithm

Define a helper:

flatten_tail(node)

This function flattens the list starting at node and returns the tail of the flattened list.

Inside the helper:

1. Set curr = node.
2. Track tail = node.
3. While curr exists:
   • Save next_node = curr.next.
   • If curr.child exists:
     • Flatten the child list.
     • Splice the child list between curr and next_node.
     • Clear curr.child.
     • Move tail to the child tail.
   • Otherwise, set tail = curr.
   • Move curr to the next node that should be processed.
4. Return tail.

The public method calls:

flatten_tail(head)

and returns head.

Correctness

The helper processes a list segment from left to right.

When the current node has no child, it already belongs in the correct flattened position. The algorithm leaves its next and prev relationship intact and moves forward.

When the current node has a child, the problem requires the child list to appear immediately after the current node and before the current node’s original next node. The algorithm saves the original next node, flattens the child list, and then splices the flattened child segment exactly between the current node and the saved next node.

The recursive call returns the tail of the flattened child segment. Therefore, reconnecting that tail to the saved next node preserves every node that originally came after the current node.

The algorithm clears the current node’s child pointer after splicing, so every processed child pointer becomes None.

By applying this rule to every node, including nodes inside child lists, the final list follows depth-first order with correct prev and next links.

Complexity

Here, n is the total number of nodes.

d is the maximum depth of child nesting.

Implementation

class Solution:
    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None

        def flatten_tail(node: 'Node') -> 'Node':
            curr = node
            tail = node

            while curr:
                next_node = curr.next

                if curr.child:
                    child_head = curr.child
                    child_tail = flatten_tail(child_head)

                    curr.next = child_head
                    child_head.prev = curr
                    curr.child = None

                    if next_node:
                        child_tail.next = next_node
                        next_node.prev = child_tail

                    tail = child_tail
                    curr = next_node
                else:
                    tail = curr
                    curr = curr.next

            return tail

        flatten_tail(head)
        return head

Code Explanation

The empty list is handled first:

if not head:
    return None

The helper function returns the final node of a flattened segment:

def flatten_tail(node: 'Node') -> 'Node':

We walk through the current level using:

curr = node
tail = node

Before changing any pointer, we save the original next node:

next_node = curr.next

This matters because if curr has a child, curr.next will be overwritten.

When a child exists:

if curr.child:

we flatten that child list first:

child_head = curr.child
child_tail = flatten_tail(child_head)

Then we place the child list immediately after the current node:

curr.next = child_head
child_head.prev = curr

The child pointer must be removed:

curr.child = None

If the current node originally had a next node, we attach it after the flattened child list:

if next_node:
    child_tail.next = next_node
    next_node.prev = child_tail

After processing a child, the last node of the flattened segment is the child tail:

tail = child_tail

Then we continue from the saved original next node:

curr = next_node

When there is no child, the current node simply becomes the latest tail:

tail = curr
curr = curr.next

At the end, the helper returns the last node of this flattened segment:

return tail

The public method flattens in-place and returns the original head:

flatten_tail(head)
return head

Testing

We can build a multilevel list manually and check the final forward and backward order.

class Node:
    def __init__(self, val, prev=None, next=None, child=None):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child

def link(values):
    nodes = [Node(v) for v in values]

    for i in range(1, len(nodes)):
        nodes[i - 1].next = nodes[i]
        nodes[i].prev = nodes[i - 1]

    return nodes

def forward_values(head):
    ans = []
    curr = head

    while curr:
        ans.append(curr.val)

        assert curr.child is None

        if curr.next:
            assert curr.next.prev is curr

        curr = curr.next

    return ans

def backward_values(head):
    curr = head

    while curr and curr.next:
        curr = curr.next

    ans = []

    while curr:
        ans.append(curr.val)

        if curr.prev:
            assert curr.prev.next is curr

        curr = curr.prev

    return ans

def run_tests():
    main = link([1, 2, 3, 4])
    child = link([5, 6])
    grandchild = link([7, 8])

    main[1].child = child[0]
    child[1].child = grandchild[0]

    head = Solution().flatten(main[0])

    assert forward_values(head) == [1, 2, 5, 6, 7, 8, 3, 4]
    assert backward_values(head) == [4, 3, 8, 7, 6, 5, 2, 1]

    single = Node(10)
    assert forward_values(Solution().flatten(single)) == [10]

    assert Solution().flatten(None) is None

    print("all tests passed")

run_tests()

Test meaning: