LeetCode LCR 028. 扁平化多级双向链表
目录
题目描述
题意分析
给一条双向链表，每个节点除了
prev和next，还可能有一个child指针指向另一条同样结构的双向链表。要求把整个多级结构压平成一条普通双向链表，压平后所有child必须置空。压平的顺序题目说得很清楚：遇到带
child的节点，就把它的子链整条插到该节点与它原来的后继之间，子链内部若还有child则继续按同样规则展开。这等价于对整棵「链 + 子链」结构做一次先序遍历。结构上要看到两点。第一，
child让这条链其实是一棵树：next是兄弟指针，child是孩子指针，题目要的就是它的先序序列。第二，插入子链会打断原来的next关系，被打断的那个后继必须先保存下来，等子链走到尽头再接回去——而子链可能嵌套很多层，需要接回去的后继也就不止一个，且接回顺序与保存顺序相反（最里层最先接回）。
prev指针不能忘。这是双向链表，每次改next都要同步维护反向指针，否则判题遍历反向时会发现断裂。边界：整条链为空直接返回空；某个节点的
child非空但它自己是尾节点（next为空），此时没有需要保存的后继；连续多个节点都带child也要能正确处理。
解法：深度优先搜索
核心思路
先想最朴素的模拟：从头往后走，一旦碰到
child，就把子链接上去，然后从子链头部继续往前走。这个动作本身很好写，难点在于「子链走完之后怎么回到原来被打断的后继」。因为嵌套可以有很多层，需要回填的后继会积累成一串，而且必须最后被打断的最先接回——第 3 层的后继要在第 2 层之前接回。这个「后进先出」的访问模式，正是栈的语义。
于是状态定义为：栈里保存的是所有已被打断、等待接回的后继节点，栈顶是最近一次被打断的那个。指针
cur表示当前正在处理的节点，且它左边的部分已经完全压平。主循环里
cur每轮只可能遇到三种情形，且互斥。其一，
cur.child非空。此时先把cur.next（如果存在）压栈存好，再把child接到cur后面并双向连好，最后必须把cur.child置空——题目要求压平后child全为空，而且不置空的话再次走到这里会无限循环。其二，
cur.next为空且栈非空。说明当前这一层走到尽头了，弹出最近保存的后继接到cur后面，双向连好，遍历自然回到上一层。其三，其余情况什么都不做，直接往后走。
三种情形处理完统一执行
cur = cur.next，因为无论哪一种，cur.next都已经被更新成「压平后的下一个节点」。当cur.next为空且栈也空时，cur变为空，循环结束，整条链压平完毕。头节点自始至终没变过，直接返回head。这个写法用显式栈替代了递归调用栈，好处是不会因为嵌套过深而爆栈，且每一步的状态都摆在明面上，白板讲解时更容易说清楚。
解题步骤
- 空链表提前返回：
head == null时返回null，后面的循环体就不必再判空。- 准备栈与游标：栈存待接回的后继，
cur从head出发。栈选ArrayDeque而不是Stack，前者没有同步开销且是官方推荐的栈实现。- 有孩子就下沉：
if (cur.child != null)。先if (cur.next != null) stack.push(cur.next)——只有存在后继才需要保存，cur是本层尾节点时压栈只会存进一个空值污染后续判断。然后cur.next = child; child.prev = cur;两句一起改，双向链表的每一次接线都是成对的。最后cur.child = null断掉孩子指针。- 走到尽头就上浮：
else if (cur.next == null && !stack.isEmpty())，弹栈得到next，同样成对地写cur.next = next; next.prev = cur;。用else if而不是独立的if，是因为刚接上孩子的节点其next必然非空，不可能同时命中两个分支。- 统一推进：
cur = cur.next。三个分支都把cur.next修好了，推进逻辑只需要写一次。- 返回
head：压平是就地完成的，头节点从未改变。以下面这个结构走一遍：主链
1 ↔ 2 ↔ 3 ↔ 4 ↔ 5 ↔ 6，节点3有子链7 ↔ 8 ↔ 9 ↔ 10，节点8又有子链11 ↔ 12。
cur = 1，无child、next非空，直接走到2；cur = 2同理走到3。cur = 3有child：把4压栈（栈内[4]），接上3 ↔ 7，清空3.child，cur走到7。cur = 7平凡，走到8。cur = 8有child：把9压栈（栈内[4, 9]，栈顶是9），接上8 ↔ 11，清空8.child，cur走到11，再走到12。
cur = 12时next为空且栈非空：弹出栈顶9（栈内剩[4]），接上12 ↔ 9，cur走到9，再走到10。cur = 10时next为空且栈非空：弹出4（栈空），接上10 ↔ 4，cur走到4，再依次走到5、6。cur = 6时next为空且栈也空，三个分支都不命中，cur = cur.next变成空，循环结束。最终序列为
1 ↔ 2 ↔ 3 ↔ 7 ↔ 8 ↔ 11 ↔ 12 ↔ 9 ↔ 10 ↔ 4 ↔ 5 ↔ 6，与先序遍历一致，且所有child都已置空，prev也在每次接线时同步维护。再看只有一个节点带孩子的最小用例
1 → child: 2：cur = 1有child但next为空，因此不压栈，接上1 ↔ 2并清空child，cur走到2；cur = 2时next为空且栈空，cur变空退出。结果1 ↔ 2，如果当时无脑压了一个空值进去，这一轮就会取出空值并对它写prev，直接空指针。
代码实现
class Solution {
public Node flatten(Node head) {
if (head == null) {
return null;
}
// 栈里存所有被子链打断、等待接回的后继，栈顶是最近打断的那个。
Deque<Node> stack = new ArrayDeque<>();
Node cur = head;
while (cur != null) {
if (cur.child != null) {
// 只有存在后继才需要保存，否则会往栈里塞空值。
if (cur.next != null) {
stack.push(cur.next);
}
Node child = cur.child;
cur.next = child;
child.prev = cur;
// 题目要求压平后 child 全为空，也避免再次下沉造成死循环。
cur.child = null;
} else if (cur.next == null && !stack.isEmpty()) {
// 本层走到尽头，接回最近一次被打断的后继。
Node next = stack.pop();
cur.next = next;
next.prev = cur;
}
cur = cur.next;
}
return head;
}
}
func flatten(root *Node) *Node {
if root == nil {
return nil
}
// 栈里存所有被子链打断、等待接回的后继，栈顶是最近打断的那个。
stack := make([]*Node, 0)
cur := root
for cur != nil {
if cur.Child != nil {
// 只有存在后继才需要保存，否则会往栈里塞空值。
if cur.Next != nil {
stack = append(stack, cur.Next)
}
child := cur.Child
cur.Next = child
child.Prev = cur
// 题目要求压平后 child 全为空，也避免再次下沉造成死循环。
cur.Child = nil
} else if cur.Next == nil && len(stack) > 0 {
// 本层走到尽头，接回最近一次被打断的后继。
next := stack[len(stack)-1]
stack = stack[:len(stack)-1]
cur.Next = next
next.Prev = cur
}
cur = cur.Next
}
return root
}
复杂度分析
- 时间复杂度：$O(n)$，
n为所有层节点总数。每个节点恰好被cur访问一次，每个节点最多入栈出栈各一次，循环体内只有常数次指针赋值与判空。- 空间复杂度：$O(d)$，
d是嵌套层数，最坏情况下每一层都只有一个带child的节点，栈会存下 $O(n)$ 个待接回的后继。递归写法的栈深度同样是 $O(d)$，两者空间量级一致，但显式栈不会触发运行时的栈溢出。
关键点总结
- 看清结构的本质：
next是兄弟、child是孩子，「压平」就是求先序遍历序列，识别出这一点后所有实现细节都有了依据。- 「被打断的后继要按相反顺序接回」直接对应栈的后进先出，这是选择数据结构最典型的推理路径，面试时要说出这层理由而不是只说「用个栈」。
- 双向链表改指针必须成对：写
a.next = b就一定紧跟b.prev = a，把两句绑成一个动作能消灭一大类隐蔽错误。- 压栈前先判断后继是否存在，避免把空值塞进栈里——「不要把无意义的状态存进数据结构」是通用原则。
cur.child = null既是题目的硬性要求，也是防止重复下沉死循环的保险，属于「功能与正确性双重必要」的一步。- 面试视角：递归写法更短，但需要返回「子链尾节点」才能接回后继，讲解时要多绕一圈；显式栈的迭代写法每一步状态可见，更适合白板。被追问哪种更好时，可以指出两者时间空间同阶，迭代版在嵌套极深时不会爆栈。
易错点总结
- 忘记
cur.child = null：主链1 ↔ 2、1带子链3时，压平后1.child仍指向3，判题直接判错；如果实现里还会重新扫描，还会在1处无限下沉。- 改
next时不同步改prev：3接上子链头7却漏写7.prev = 3，正向遍历看起来正确，反向遍历时从7回不到3，结果被判错。cur.next为空时也压栈：1带子链2且1是尾节点，栈里被塞进一个空值，后续弹出后执行next.prev = cur直接空指针异常。- 接子链前不保存
cur.next：先执行cur.next = child再想取后继，原来的4 ↔ 5 ↔ 6整段丢失，输出只剩子链部分。- 两个分支都写成独立的
if：刚接上子链的节点next非空，第二个if的条件本就不成立，虽然不会出错，但一旦把条件误写成!stack.isEmpty()就会在接上子链后又弹一个后继，把栈里的节点提前接到错误位置。- 用队列代替栈：
1带子链7 ↔ 8、8带子链11的结构里，先进先出会先接回外层的后继，得到... 11 ↔ 4 ...这种越级顺序，先序关系被破坏。- 递归写法只返回头节点不返回尾节点：子链展开后调用方不知道该把后继接到哪里，只能再遍历一次找尾，退化成 $O(n^2)$。
- 在遍历中途修改
cur.child之外还顺手改了cur.prev：头节点的prev必须保持为空，误写会让判题在校验链表头时失败。- 循环推进写成
cur = cur.child或另起分支推进：三个分支已经把cur.next修好，额外的推进逻辑会跳过刚接上的节点，1 ↔ 2带子链的结构会漏掉子链首节点。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 430. 扁平化多级双向链表 | 中等 | 与本题同题，可直接套用显式栈写法 |
| 114. 二叉树展开为链表 | 中等 | 同样把树按先序压平成链，但只有单向 right 指针，无需维护 prev
|
| 341. 扁平化嵌套列表迭代器 | 中等 | 同样的嵌套展开，但要求做成迭代器，按需产出而不是一次性压平 |
| 426. 将二叉搜索树转化为排序的双向链表 | 中等 | 换成中序遍历建双向链表，且要首尾相连成循环链表 |
| 138. 随机链表的复制 | 中等 | 同样是多指针链表，但要处理的是深拷贝时的引用映射而非展开顺序 |
| 707. 设计链表 | 中等 | 双向链表增删改的基本功，本题「成对改 next 与 prev」的手感来源 |