# 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:

| Field | Meaning |
|---|---|
| `val` | Node value |
| `prev` | Previous node on the same level |
| `next` | Next node on the same level |
| `child` | Head of another doubly linked list |

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

| Item | Meaning |
|---|---|
| Input | `head`, the head of the first-level doubly linked list |
| Output | The same head, after flattening |
| Required order | Depth-first order |
| Pointer rule | Preserve valid `prev` and `next` links |
| Child pointers | All must become `None` |
| Empty list | Return `None` |

The node class is usually:

```python
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:

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

The flattened list should be:

```text
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:

```python
head = None
```

the answer is:

```python
None
```

## First Thought: Collect Nodes

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

For example:

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

Then we can reconnect them:

```text
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:

```text
curr - next
 |
child
```

After flattening, we want:

```text
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:

```python
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:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each node is visited once |
| Space | `O(d)` | Recursion depth follows nested child depth |

Here, `n` is the total number of nodes.

`d` is the maximum depth of child nesting.

## Implementation

```python
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:

```python
if not head:
    return None
```

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

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

We walk through the current level using:

```python
curr = node
tail = node
```

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

```python
next_node = curr.next
```

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

When a child exists:

```python
if curr.child:
```

we flatten that child list first:

```python
child_head = curr.child
child_tail = flatten_tail(child_head)
```

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

```python
curr.next = child_head
child_head.prev = curr
```

The child pointer must be removed:

```python
curr.child = None
```

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

```python
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:

```python
tail = child_tail
```

Then we continue from the saved original next node:

```python
curr = next_node
```

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

```python
tail = curr
curr = curr.next
```

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

```python
return tail
```

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

```python
flatten_tail(head)
return head
```

## Testing

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

```python
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:

| Test | Why |
|---|---|
| Nested child list | Checks depth-first flattening |
| Forward traversal | Checks `next` links |
| Backward traversal | Checks `prev` links |
| `child is None` assertion | Confirms all child pointers are cleared |
| Single node | Checks smallest non-empty list |
| Empty list | Checks `None` handling |