多级双向链表如何扁平化？child 指针应该怎么处理？

简化版

多级双向链表扁平化就是把 child 子链插入到当前节点和 next 之间，并保持深度优先顺序。处理完子链后要把子链尾接回原来的 next，同时清空 child 指针。

详细版

多级双向链表节点通常有 prev、next、child 三类指针。扁平化要求把所有节点变成一条普通双向链表。

常见 DFS 思路：

遍历当前层节点。
遇到 cur.child 时，先保存 next = cur.next。
扁平化 child 子链，拿到子链头和尾。
把 cur.next 接到 child 头，child 头的 prev 接回 cur。
子链尾再接回原 next。
最后 cur.child = null。

复杂度是 O(n)，每个节点处理一次；递归 DFS 的栈空间和嵌套深度有关，最坏 O(n)。

完整版教学

一、多级链表多出来的难点是什么

普通双向链表只有前后两个方向，而多级双向链表还多了 child 指针。这个 child 指向一条子链，子链里的节点也可能继续有 child。

结构可以像这样：

1 - 2 - 3 - 4
    |
    7 - 8
        |
        11 - 12

扁平化后如果按深度优先，结果应是 1 - 2 - 7 - 8 - 11 - 12 - 3 - 4。难点不是访问所有节点，而是插入 child 子链后还能把原来的 next 接回来。

二、为什么要先保存原 next

当 cur 有 child 时，cur.next 原本指向当前层后续节点。如果你直接把 cur.next = cur.child，原来的后续节点入口就丢了。

安全做法：

const next = cur.next;
const childHead = cur.child;
// 扁平化 child，得到 childTail
cur.next = childHead;
childHead.prev = cur;
cur.child = null;
childTail.next = next;
if (next) next.prev = childTail;

这里 next 就像临时书签。你先把当前层后半段保存起来，等 child 子链全部接完，再把书签接到 child 尾部。

三、DFS 顺序为什么符合题意

多数多级链表扁平化要求是：遇到 child，先完整展开 child，再回到原来的 next。这个顺序就是深度优先遍历。

用上面的例子看：

访问 1
访问 2，发现 child=7
进入 7
访问 8，发现 child=11
进入 11、12
回到 3、4

如果你先继续走 next，最后再拼 child，就会得到层序味道的结果，顺序不符合常见题意。面试时要先确认“扁平化顺序”，如果题目没说清，通常默认 DFS。

四、递归函数为什么常返回尾节点

扁平化 child 后，必须知道 child 子链的尾巴，才能把原来的 next 接上。递归函数如果只返回头节点，还要再次遍历 child 子链找尾，效率会变差。

更好的递归语义是：给我一段链表头，我负责扁平化它，并返回这段扁平链表的尾节点。

返回内容	后续接链成本	评价
只返回头	还要找尾，可能重复遍历	不推荐
返回尾	可直接接回原 next	稳定
返回头尾对	信息最完整	代码稍长

这样每个节点仍然只处理常数次，总体 O(n)。

五、为什么 child 必须清空

扁平化后的目标是一条普通双向链表，节点不应该再保留 child 指针。如果不清空，结构上仍然是多级链表，后续遍历或序列化可能重复访问节点。

例如节点 2.child 仍指向 7，而 2.next 也已经指向 7。这会让同一节点有两条入口路径，调试时很容易误判成环或重复链。

正确状态：2.next = 7, 2.child = null
错误状态：2.next = 7, 2.child = 7

清空 child 是语义收尾，不只是格式要求。

六、复杂度和迭代实现

递归 DFS 简洁，但深度很大时可能栈溢出。迭代写法可以用显式栈保存原来的 next，遇到 child 就先压入 next，再走 child；child 走完后从栈中弹出继续。

记忆钩子：多级链表扁平化的口诀是“保存 next、插入 child、尾巴接回、清空 child”。

七、常见误区与追问

误区：把 child 接到 next 就结束了。 还要找到 child 扁平化后的尾节点，并接回原来的 next。
误区：不用清空 child。 扁平化后 child 应该为 null，否则结构仍然不是普通链表。
误区：双向链表只维护 next。 必须同步维护 prev，否则反向遍历会坏。
追问：递归会不会栈溢出？ 嵌套层级很深时会，可以改成显式栈迭代。
追问：顺序是 DFS 还是 BFS？ 常见定义是 DFS；如果题目要求层序，需要重新设计拼接顺序。

八、加强记忆

多级双向链表扁平化像把书里的脚注插回正文：读到 child 就先展开脚注，展开完再接回原文。实现时关键变量是原 next 和 child 扁平化后的尾节点；关键收尾是维护 prev 并清空 child。

简化版

详细版