友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
430. 扁平化多级双向链表
你会得到一个双链表，其中包含的节点有一个下一个指针、一个前一个指针和一个额外的 子指针。这个子指针可能指向一个单独的双向链表，也包含这些特殊的节点。这些子列表可以有一个或多个自己的子列表，以此类推，以生成如下面的示例所示的 多层数据结构。
给定链表的头节点 head ，将链表 扁平化 ，以便所有节点都出现在单层双链表中。让 curr 是一个带有子列表的节点。子列表中的节点应该出现在扁平化列表中的 curr 之后 和 curr.next 之前 。
返回 扁平列表的 head 。列表中的节点必须将其 所有 子指针设置为 null 。
示例 1：
输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12] 输出：[1,2,3,7,8,11,12,9,10,4,5,6] 解释：输入的多级列表如上图所示。 扁平化后的链表如下图：
示例 2：
输入：head = [1,2,null,3] 输出：[1,3,2] 解释：输入的多级列表如上图所示。 扁平化后的链表如下图：
示例 3：
输入：head = [] 输出：[] 说明：输入中可能存在空列表。
提示：
-
节点数目不超过
1000 -
1 <= Node.val <= 105
如何表示测试用例中的多级链表？
以 示例 1 为例：
1---2---3---4---5---6--NULL
|
7---8---9---10--NULL
|
11--12--NULL
序列化其中的每一级之后：
[1,2,3,4,5,6,null] [7,8,9,10,null] [11,12,null]
为了将每一级都序列化到一起，我们需要每一级中添加值为 null 的元素，以表示没有节点连接到上一级的上级节点。
[1,2,3,4,5,6,null] [null,null,7,8,9,10,null] [null,11,12,null]
合并所有序列化结果，并去除末尾的 null 。
[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
思路分析
深度优先遍历，逐个元素处理，遇到有子元素的情况，则“向下”一层，将下一层做扁平化处理。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-08-13 22:12:36
*/
public Node flatten(Node head) {
Node dummy = new Node();
dummy.next = head;
while (head != null) {
if (head.child == null) {
head = head.next;
} else {
Node temp = head.next;
// 由于 flatten 返回 head，导致每个子元素最多要被访问 h 次
// 可以优化一下，返回 tail，这样每个元素只需要访问一次。
Node chead = flatten(head.child);
head.next = chead;
chead.prev = head;
head.child = null;
while (head.next != null) {
head = head.next;
}
head.next = temp;
if (temp != null) {
temp.prev = head;
}
head = temp;
}
}
return dummy.next;
}