# 430. Flatten a Multilevel Doubly Linked List

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. 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.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

**Example:**

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

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

**Explanation for the above example:**

Given the following multilevel doubly linked list:

![](/files/-LqdhDpsAY2mT37i-lEK)

We should return the following flattened doubly linked list:

![](/files/-LqdhHx9Dy_8vlLmN5W3)

```cpp
// Iteration
Node* flatten(Node* head) { // time: O(n); space: O(1)
    if (!head) return nullptr;
    Node* p = head;
    while (p) {
        // no child
        if (!p->child) {
            p = p->next;
            continue;
        }
        // has child
        Node* tmp = p->child;
        // connect the tail of child to the next p
        while (tmp->next) {
            tmp = tmp->next;
        }
        tmp->next = p->next;
        if (p->next) p->next->prev = tmp;
        // connect p to p->child and remove p->child
        p->next = p->child;
        p->child->prev = p;
        p->child = nullptr;
    }
    return head;
}
```

```cpp
// Iteration
Node* flatten(Node* head) { // time: O(n); space: O(1)
    Node* cur = head;
    while (cur) {
        if (cur->child) {
            Node* next = cur->next;
            Node* last = cur->child;
            while (last->next) {
                last = last->next;
            }
            cur->next = cur->child;
            cur->next->prev = cur;
            cur->child = nullptr;
            last->next = next;
            if (next) next->prev = last;
        }
        cur = cur->next;
    }
    return head;
}
```

```cpp
// Recursion
Node* flatten(Node* head) { // time: O(n); space: O(n)
    Node* cur = head;
    while (cur) {
        if (cur->child) {
            Node* next = cur->next;
            cur->child = flatten(cur->child);
            Node* last = cur->child;
            while (last->next) last = last->next;
            cur->next = cur->child;
            cur->next->prev = cur;
            cur->child = nullptr;
            last->next = next;
            if (next) next->prev = last;
        }
        cur = cur->next;
    }
    return head;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/tree/430.-flatten-a-multilevel-doubly-linked-list.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.