# LeetCode 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.

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

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

### 解题思路：

 1---2---3---4---5---6--NULL
|
7---8---9---10--NULL
|
11---12---NULL
从节点 1 开始遍历，当前遍历链表为：1---2---3---4---5---6--NULL

Java:

class Solution {
}
//深度优先搜索函数
while (cur != null) {
if (cur.child != null) {
//改变当前节点与子节点的关系
Node next = cur.next;//记录暂存下一个节点
cur.next = cur.child;//当前节点与子链表头节点连接
cur.next.prev = cur;
//传递子链表头节点作为参数到 dfs
Node childLast = dfs(cur.child);//childLast获得返回值为子链表的尾节点
childLast.next = next;//子链表尾节点与暂存节点连接
if (next != null) next.prev = childLast;//暂存节点不为空就将其prev指向子链表尾节点
cur.child = null;//子链表置空
cur = childLast;//刷新当前节点，跳过子链表的遍历
}
cur = cur.next;//刷新当前节点
}
}
}

Python3:

class Solution:
def flatten(self, head: 'Node') -> 'Node':

while cur:
if cur.child:
next = cur.next
cur.next = cur.child
cur.next.prev = cur
childLast = self.dfs(cur.child)
childLast.next = next
if next: next.prev = childLast
cur.child = None
cur = cur.next
return head

|
1月前
|

LeetCode力扣第114题：多种算法实现 将二叉树展开为链表
LeetCode力扣第114题：多种算法实现 将二叉树展开为链表
17 0
|
15天前
|
Java

14 2
|
15天前
|
Java

10 1
|
15天前
|

12 1
|
28天前
|

[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
18 2
|
1月前
|
Java Python

16 1
|
1月前
|

LeetCode 题目 86：分隔链表
LeetCode 题目 86：分隔链表
20 2
|
1月前
|

19 1
|
1月前
|
SQL 算法 数据可视化
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
21 1
|
15天前
|
Java 索引

10 0