# 430     Flatten a Multilevel Doubly Linked List

## 430. [Flatten a Multilevel Doubly Linked List](https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/description/)

## 1. Question

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

## 2. Implementation

```java
/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;

    public Node() {}

    public Node(int _val,Node _prev,Node _next,Node _child) {
        val = _val;
        prev = _prev;
        next = _next;
        child = _child;
    }
};
*/
class Solution {
    public Node flatten(Node head) {
        if (head == null) {
            return head;
        }

        Node curNode = head;

        while (curNode != null) {
            if (curNode.child == null) {
                curNode = curNode.next;
            }
            else {
                Node temp = curNode.child;

                while (temp.next != null) {
                    temp = temp.next;
                }

                temp.next = curNode.next;

                if (curNode.next != null) {
                    curNode.next.prev = temp;
                }
                curNode.next = curNode.child;
                curNode.child.prev = curNode;
                curNode.child = null;
            }
        }
        return head;
    }
}
```

## 3. Time & Space Complexity

时间复杂度O(n), n是linked list总共node的个数，空间复杂度O(1)


---

# 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://protegejj.gitbook.io/oj-practices/chapter1/linked-list/430-flatten-a-multileveldoubly-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.