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




We should return the following flattened doubly linked list:
```

分析

dfs返回首尾，记得如果有儿子，返回的tail是儿子的tail

```
"""
# Definition for a Node.
class Node:
    def __init__(self, val, prev, next, child):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child
"""
class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        if not head:
            return head       
        def dfs(head):
            cur = head
            tail = None
            while cur:
                if cur.child:
                    h,e = dfs(cur.child)
                    cur.child = None
                    nxt = cur.next
                    cur.next = h
                    h.prev = cur
                    e.next = nxt
                    if nxt:                      
                        nxt.prev = e
                    cur = nxt
                    tail = e #tail有child的要指向e！！！！！
                else:
                    tail = cur  #否则指向最后一个item            
                    cur = cur.next

            return (head, tail)        


        h,e = dfs(head)
        return h
```


---

# 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://nataliekung.gitbook.io/ladder_code/dfs/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.