> For the complete documentation index, see [llms.txt](https://luj.gitbook.io/code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://luj.gitbook.io/code/data-structure/linkedlist/flatten-a-multilevel-doubly-linked-list.md).

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

## Note

**迭代法：**

直接改吧，找到有child的节点curr，找到这一层的tail，连到curr的后面（注意断开或者新连接都是双向的）对于不同层次的在下次会被访问，相当于level一直在减少

**递归法：**

对于链表，递归执行顺序不一样，返回第一层的时候，下面几层都已经搞好了。递归的参数往往是下一个节点。帮助函数返回必须得是tail了这里，所以需要一个帮助函数，因为主函数返回的是head。

## Code

```java
public Node flatten(Node head) {
    if (head == null) {
        return head;
    }

    Node curr = head;
    while (curr != null) {
        if (curr.child == null) {
            curr = curr.next;
            continue;
        } else {
            Node c = curr.child;
            Node next = curr.next;

            curr.next = c;
            c.prev = curr;
            while (c.next != null) {
                c = c.next;
            }
            if (next != null) {
                c.next = next;
                next.prev = c;
            }
            curr.child = null;
        }
    }

    return head;
}
```

```java
public Node flatten(Node head) {
    helper(head);
    return head;
}

private Node helper(Node head) {
    Node cur = head, pre = head;
    while (cur != null) {
        if (cur.child == null) {
            pre = cur;
            cur = cur.next;
        } else {
            Node tmp = cur.next;
            Node child = helper(cur.child);
            cur.next = cur.child;
            cur.child.prev = cur;
            cur.child = null;
            child.next = tmp;
            if (tmp != null) tmp.prev = child;
            pre = child;
            cur = tmp;
        }
    }
    return pre;
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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://luj.gitbook.io/code/data-structure/linkedlist/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.