> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Flatten a Multilevel Doubly Linked List

> Tested Python solution for LeetCode 430 with 20 pytest cases. Generate a practice environment with lcpy.

LeetCode 430, [Medium](/catalog/medium). Topics: [Linked List](/catalog/topics/linked-list), [Depth-First Search](/catalog/topics/depth-first-search), Doubly-Linked List. [View on LeetCode](https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/description/).

Generate this problem as a practice environment: tested reference solution, 20 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 430   # by problem number
lcpy gen -s flatten_a_multilevel_doubly_linked_list   # by problem name
```

## Problem

You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional **child pointer**. This child pointer may or may not point to a separate doubly linked list, also containing these special nodes. These child lists may have one or more children of their own, and so on, to produce a **multilevel data structure** as shown in the example below.

Given the `head` of the first level of the list, **flatten** the list so that all the nodes appear in a single-level, doubly linked list. Let `curr` be a node with a child list. The nodes in the child list should appear **after** `curr` and **before** `curr.next` in the flattened list.

Return the head of the flattened list. The nodes in the list must have all of their child pointers set to `null`.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2021/11/09/flatten11.jpg)

```
Input: head = [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]
Explanation: The multilevel linked list in the input is shown.
After flattening the multilevel linked list it becomes:
```

![Flattened list](https://assets.leetcode.com/uploads/2021/11/09/flatten12.jpg)

![Example 2](https://assets.leetcode.com/uploads/2021/11/09/flatten2.1jpg)

```
Input: head = [1,2,null,3]
Output: [1,3,2]
Explanation: The multilevel linked list in the input is shown.
After flattening the multilevel linked list it becomes:
```

![Flattened list](https://assets.leetcode.com/uploads/2021/11/24/list.jpg)

```
Input: head = []
Output: []
Explanation: There could be empty list in the input.
```

### Constraints

* The number of Nodes will not exceed 1000.
* 1 \<= Node.val \<= 10^5

**How the multilevel linked list is represented in test cases:**

We use the multilevel linked list from Example 1 above:

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

The serialization of each level is as follows:

```
[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]
```

To serialize all levels together, we will add nulls in each level to signify no node connects to the upper node of the previous level. The serialization becomes:

```
[1,    2,    3, 4, 5, 6, null]
             |
[null, null, 7,    8, 9, 10, null]
                   |
[            null, 11, 12, null]
```

Merging the serialization of each level and removing trailing nulls we obtain:

```
[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
```

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/flatten_a_multilevel_doubly_linked_list/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/flatten_a_multilevel_doubly_linked_list/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from __future__ import annotations


class Node:
    def __init__(
        self,
        val: int = 0,
        prev: Node | None = None,
        next: Node | None = None,
        child: Node | None = None,
    ) -> None:
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child


class Solution:
    # Time: O(n) per level splice, O(n * depth) worst case
    # Space: O(1)
    def flatten(self, head: Node | None) -> Node | None:
        node = head
        while node is not None:
            if node.child is None:
                node = node.next
                continue
            child = node.child
            node.child = None
            nxt = node.next
            node.next = child
            child.prev = node
            tail = child
            while tail.next is not None:
                tail = tail.next
            tail.next = nxt
            if nxt is not None:
                nxt.prev = tail
            node = child
        return head
```

## Complexity

| Time | Space |
| - | - |
| O(n) per level splice, O(n \* depth) worst case | O(1) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.