# 430. 扁平化多级双向链表

<https://leetcode-cn.com/problems/flatten-a-multilevel-doubly-linked-list/>

## 解法一：dfs

dfs遍历链表，遇到有孩子的节点i就递归其子链，并将其子链插入i之后

```python
"""
# 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':
        self.dfs(head)
        return head
    
    def dfs(self, head):
        i = head
        pre = None
        while i:
            if i.child:
                childLast = self.dfs(i.child)   #对子链递归，返回子链尾
                
                #子链末尾与i后继街上
                childLast.next = i.next
                if i.next:  #若i后继不为空，修改后继的前驱
                    i.next.prev = childLast                
                    
                #i后继改为子链头
                i.next = i.child
                i.child.prev = i
                #i子项置空
                i.child = None
                #跳过子链
                i = childLast
            pre = i
            i = i.next
        return pre  #本级返回链尾
```


---

# 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://cai-sen-se.gitbook.io/leetcode/401-600/430.-bian-ping-hua-duo-ji-shuang-xiang-lian-biao.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.