LeetCode LCR 028. 扁平化多级双向链表

2026-03-28 HGNULB 约 5 分钟

文章信息 5 个分类 4 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 028. 扁平化多级双向链表

题意分析

多级双向链表的节点有 prev、next 和 child。需要将所有层展开成一条双向链表，保留原节点，并将全部 child 清空。

遇到有子链的节点时，先完整展开它的子链，再继续访问原来的后继；子链内部按相同规则处理。最终不仅正向顺序正确，反向 prev 连接也要与之对应。

解法：显式栈深度优先展平

核心思路

[!blue]

从头向后扫描，遇到子链就应立即进入，而原后继需要暂时推迟。嵌套层里的后继必须比外层后继先恢复，这种后进先出的顺序正好由栈保存。

用 cur 表示当前节点，栈保存已经被子链打断、尚待接回的后继。若当前有 child，先把非空原后继压栈，再令当前的 next 指向子链头，并令子链头的 prev 指回当前节点，随后清空当前 child。

清空 child 是扁平结果的要求，表示这份层级关系已经转成普通相邻连接。当前遍历只沿更新后的 next 前进，不能把这一步的作用误说成算法必然会重新访问父节点。

没有子链且当前 next 为空时，说明这一段已经走完。如果栈非空，就取最近保存的后继，成对设置 cur.next 与 next.prev，继续内层尚未处理部分；栈空则表示全部展开结束。

每次处理完都统一沿 cur.next 前进，因为它现在恰好是深度优先顺序中的下一个节点。进入子链前已经处理的部分顺序固定，待恢复部分由栈保存，所以不会丢节点或提前跳过内层。原头不改变，结束后直接返回。

解题步骤

空链直接返回空，创建空栈，游标从头开始。

有子链时，先保存非空原后继，再把子链接到当前节点后面，维护反向连接并清空 child。

无子链且走到当前段末尾时，若栈中还有后继，就弹出并双向接回。

沿更新后的 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;
                // 层级连接已经转为普通后继，按题意清空 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$ 为全部层的节点数。每个节点访问一次，每个被推迟的后继至多入栈、出栈各一次。

空间复杂度：$O(d)$，其中 $d$ 为嵌套深度，栈每个活跃层至多保存一个待接回的后继；当多层都留有后继时最坏可达 $O(n)$。

关键点总结

[!green]

子链优先、原后继稍后，等价于深度优先的展开顺序。

栈让最近被打断的后继最先恢复，保持嵌套层次。

双向接线必须同时维护前后两个方向。

层级边转为普通连接后清空 child，满足最终结构要求。

易错点总结

[!yellow]

下沉前不保存原后继，会丢掉当前层尚未处理的部分。

使用先进先出的队列恢复后继，会让外层内容提前插入内层，破坏要求顺序。

只修改 next 不修正对应 prev，正向看似正确但双向结构已经断裂。

child 仍有值即不符合扁平化结果，即使正向节点顺序正确也不够。

原后继为空时无需入栈，Java 的 ArrayDeque 也不接受空元素。

相似题目

题目	难度	关联与区别
114. 二叉树展开为链表	中等	同样把树形层级结构改成线性链，本题还需维护prev并将child清空。
341. 扁平化嵌套列表迭代器	中等	同样按深度优先顺序展开嵌套结构，原题只提供迭代访问，本题实际修改链表指针。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/76851163

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！