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

2023-08-29 HGNULB 约 9 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

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

题意分析

给的链表每个节点除了 prev 和 next，还多一个 child 指针，指向另一条结构完全相同的双向链表。要求把这棵「链表构成的树」压成一条单层双向链表。

顺序规则藏在题目给的样例里：走到一个带 child 的节点时，要先把它的子链整条走完（子链里若还有 child，同样先展开），走完再回来接它原本的 next。这就是一次深度优先遍历，而且是先序的。

除了顺序，还有两条容易被忽略的硬性要求。其一，展平后所有节点的 child 必须置为 null，否则返回的仍是多级结构。其二，结果必须是合法的双向链表，也就是每一处 prev 都要和 next 对上，只改 next 不改 prev 会被判错。

边界情况包括：head 为空；带 child 的节点恰好是本层最后一个节点，此时没有需要保存的后继；嵌套层数可以很深；子链自身长度可以为 $1$。

解法：栈模拟 DFS

核心思路

最自然的想法是递归：遇到 child 就递归展平子链，然后把子链接在当前节点之后。麻烦在于接回——递归展平完子链后，还得知道子链的尾节点是谁，才能把原来的 next 续上。这意味着递归函数要额外返回尾指针，或者返回后再走一遍子链找尾，前者写法啰嗦，后者会让复杂度退化。

换个角度看这件事：真正需要「记住」的信息只有一条，就是那些被暂时搁置、等会儿要接回来的 next 节点。而它们的恢复顺序恰好是「后搁置的先恢复」——越深层的分支越先走完，也越先需要接回。这正是栈的语义，于是可以把递归的调用栈显式化，整个遍历压平成一重循环。

循环维持的不变量是：cur 及其之前的所有节点已经排成最终答案的前缀，它们的 prev / next 都已正确对接，且 child 全部为 null；栈中从栈顶到栈底，依次是等待接回的分支后继，栈顶对应最内层、最先该被恢复的那一个。每一步只需看 cur 的局部形态就能决定动作：有 child 就下沉，无 child 且走到本段尽头就弹栈上浮，否则平移。

解题步骤

先处理 head 为空的情况直接返回，避免后续解引用空指针。随后用 cur 从 head 出发，配一个空栈。

当 cur.child 非空时，说明要下沉。若 cur.next 也非空，先把它压栈——这是唯一会在下沉后丢失的信息，不存下来就再也找不回来了；若 cur.next 为空则无需压栈，少压一个空值能让后面的弹栈条件更干净。

接着把子链头接到 cur 之后：cur.next = child 与 child.prev = cur 必须成对写，只写一半就破坏了双向性。然后立刻把 cur.child 置空，因为这条边已经被「消费」成了 next 边，留着就会让结果仍是多级结构。

当 cur.child 为空且 cur.next 也为空时，说明当前这一段走到了尽头。此时若栈非空，弹出栈顶节点接到 cur 后面，同样成对更新 next 与 prev。若栈为空则说明整条链已经走完，cur = cur.next 自然得到 null，循环结束。

上述三种情况处理完统一执行 cur = cur.next 前进一格。注意「下沉」这一支执行完后 cur.next 已经是子链头，所以这一句同时承担了下沉、上浮和平移三种移动，不需要分别写。

循环结束后返回 head。头节点自始至终没被换过，因为展平只会在它后面追加内容。

以 [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12] 走一遍：这条数据描述的结构是主链 $1 \leftrightarrow 2 \leftrightarrow 3 \leftrightarrow 4 \leftrightarrow 5 \leftrightarrow 6$，节点 $3$ 的 child 指向 $7 \leftrightarrow 8 \leftrightarrow 9 \leftrightarrow 10$，节点 $8$ 的 child 指向 $11 \leftrightarrow 12$。cur = 1，无 child，next 非空，平移到 $2$；$2$ 同理平移到 $3$。cur = 3 时 child 为 $7$，next 为 $4$ 非空，把 $4$ 压栈得到栈 [4]，然后接 $3 \to 7$、$7.prev = 3$、$3.child = null$，cur 前进到 $7$。$7$ 无 child 且 next 为 $8$，平移到 $8$。cur = 8 时 child 为 $11$，next 为 $9$ 非空，压栈得到 [4, 9]（栈顶是 $9$），接 $8 \to 11$、$11.prev = 8$、8.child = null，前进到 $11$。$11$ 平移到 $12$。cur = 12 时无 child 且 next 为空，栈非空，弹出栈顶 $9$，接 $12 \to 9$、$9.prev = 12$，栈剩 [4]，前进到 $9$。$9$ 平移到 $10$。cur = 10 时无 child 且 next 为空，弹出 $4$，接 $10 \to 4$、$4.prev = 10$，栈空，前进到 $4$。$4$ 平移到 $5$，$5$ 平移到 $6$。cur = 6 时无 child、next 为空且栈为空，cur 变为 null，循环结束。最终链为 $1 \leftrightarrow 2 \leftrightarrow 3 \leftrightarrow 7 \leftrightarrow 8 \leftrightarrow 11 \leftrightarrow 12 \leftrightarrow 9 \leftrightarrow 10 \leftrightarrow 4 \leftrightarrow 5 \leftrightarrow 6$，与期望输出一致。

代码实现

// 继续向前走，若链表走到尽头，则从栈中弹出之前保存的 next 接回。
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;
                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;
    }
}

// 继续向前走，若链表走到尽头，则从栈中弹出之前保存的 next 接回。
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
            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 沿着最终链条单向前进，每个节点恰好被 cur 访问一次；每次访问内部只有常数次指针赋值和至多一次入栈或出栈，而每个节点至多入栈一次、出栈一次。

空间复杂度：$O(d)$，$d$ 为链表的最大嵌套深度，最坏情况下每个节点都带 child 从而 $d = O(n)$。栈中保存的是尚未接回的分支后继，同一时刻栈内元素个数等于当前所处的嵌套层数。

关键点总结

递归转迭代的关键判断是「递归返回后还需要什么」。这里返回后只需要一个被搁置的 next 节点，信息量极小，所以显式栈只存节点即可，不必模拟完整的调用帧。

处理双向链表时把 next 与 prev 的更新写成紧挨着的一对，是最省心的自律。分开写、或者只在最后统一补 prev，是这类题最高发的错误来源。

消费掉的结构信息要立刻清理。cur.child = null 不是收尾工作，而是循环不变量的一部分——不清就没法用「child 是否为空」来驱动状态判断。

让一句 cur = cur.next 同时承担下沉、平移、上浮三种语义，靠的是每个分支都提前把 cur.next 修成了正确的后继。这种「先修好指针再统一前进」的写法能显著压缩分支数量。

面试视角：面试官通常会追问「递归怎么写」以及「递归为什么不如迭代顺手」。答出「递归需要额外返回子链尾指针」这一点，比单纯背下迭代模板更能证明理解。

面试视角：写完主动用一个三层嵌套的小样例口述验证，重点展示栈的深度变化，能一次性打消面试官对上浮顺序是否正确的疑虑。

易错点总结

错误写法：接子链时只写 cur.next = child 而漏掉 child.prev = cur → 对 [1,2,null,3] 这类数据（节点 $2$ 的 child 为 $3$），从头正向遍历看起来完全正确，但反向沿 prev 走时 $3$ 的前驱仍是 null，判题按双向链表校验会失败。

错误写法：忘记 cur.child = null → 结构顺序对了，但返回的链表里节点 $3$ 仍挂着 child，不满足「单层链表」的要求，直接判错。

错误写法：cur.child 非空时无条件把 cur.next 压栈 → 当带 child 的节点是本层最后一个（next 为 null）时，栈里混入一个空值，后续弹栈会把 null 当成节点解引用赋 prev，抛空指针异常。

错误写法：用队列代替栈 → 对节点 $3$ 有 child、节点 $8$ 也有 child 的嵌套结构，先搁置的外层 next 会被先恢复，导致内层子链没走完就跳回外层，输出顺序完全错乱。

错误写法：先接子链再压 next → 此时 cur.next 已经被改成了子链头，压进栈的是子链头而不是原后继，原本的后半段链条彻底丢失。

错误写法：弹栈条件写成「栈非空」而不带 cur.next == null → 走到 $3$ 的子链中间时就把外层的 $4$ 接了上去，把还没走完的子链后半段截断。

错误写法：head 为空时不特判就进入循环并最后 return head → Java 侧其实能侥幸通过（循环体不执行），但若实现中先访问了 head.child 做预处理则直接崩溃，稳妥做法是开头就返回。

错误写法：递归版本里展平子链后直接用「子链头的原始尾节点」接回 next → 若子链内部还有更深的 child，展平后真正的尾节点已经变了，接回位置会落在链条中间，后半段丢失。

错误写法：为了「一次遍历」而在下沉时不移动 cur，指望下一轮循环重新判断 → 由于 cur.child 已被置空，下一轮会走到「无 child」分支并平移，虽然结果碰巧正确，但多绕一轮且逻辑难以自证，不如直接前进清晰。

错误写法：返回子链头或返回 cur 而非原 head → 展平过程从不改变头节点，返回别的节点会丢掉整个前缀。

相似题目

题目	难度	考察点
LCR 028. 扁平化多级双向链表	中等	同一题的另一入口，可用来对拍递归写法与迭代写法的输出
114. 二叉树展开为链表	中等	展平对象是二叉树，可用 Morris 思路把右子树挂到左子树最右端
341. 扁平化嵌套列表迭代器	中等	展平结果按需惰性产出，栈里存的是迭代器而非待接回的节点
426. 将二叉搜索树转化为排序的双向链表	中等	中序遍历中原地改指针，需要额外维护前驱节点并最终首尾成环
138. 随机链表的复制	中等	同样是额外指针的链表，但难点在深拷贝时的旧节点到新节点映射