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

2023-08-29 HGNULB 约 5 分钟

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

分类

LeetCode CodeTop 中等 未解决 2-5 字节 快手

标签

深度优先搜索 链表 双向链表

题目描述

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

题意分析

将多级双向链表改成单层双向链表。当前节点有子链时，要把整条子链及其更深层节点插在当前节点与原后继之间；结果中的所有 child 都为空，next 和 prev 必须互相对应。

解法：栈模拟 DFS

核心思路

[!blue]

要求的顺序是「当前节点、完整子链、原后继」，也就是子链优先的深度优先遍历。进入子链时，原后继暂时不能访问，但它还要在子链结束后接回来，因此用栈保存这些待续后继。

遇到 child 时，先把非空的原 next 入栈，再让 cur.next 指向子链头，同时把子链头的 prev 指回 cur，最后清空 cur.child。这样下一步沿 next 前进就会进入子链，原后继也不会丢失。

如果当前节点既没有子链，也没有后继，说明当前分支已走完。这时从栈顶取出最近保存的后继，成对连接 cur.next 和后继的 prev，再继续遍历。必须后进先出，因为内层子链结束后，应先恢复最近一层被搁置的部分，之后才轮到更外层。

每轮开始时，cur 之前的节点已经按要求排好，所有待续部分都保存在栈中。当前轮只确定下一条正确连接，再沿修改后的 next 前进，因此既不会漏掉原后继，也不会提前跳过子链。最终走到空指针时，栈也已清空，所有节点都已接成单链，头节点保持不变。

解题步骤

1. 空链表直接返回空；否则令 cur 指向头节点，创建空栈。
2. 当前有子链时，先保存非空原后继，再接入子链头，修复反向链接并清空 child。
3. 当前没有子链且 next 为空时，若栈非空，就弹出最近的待续后继并接回。
4. 沿更新后的 next 前进，直到 cur 为空，返回原头节点。

代码实现

// 继续向前走，若链表走到尽头，则从栈中弹出之前保存的 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)$，每个节点访问一次，待续后继至多入栈、出栈各一次。
• 空间复杂度：$O(n)$，最坏情况下，栈保存线性数量的待续后继。

关键点总结

[!green]

• 栈中保存待恢复的后继，不是已经处理的所有节点。
• 连接边时同步修改 next 与 prev。
• 后进先出保证先完成内层子链，再恢复外层后继。
• 每次都沿修改后的 next 前进，整个过程直接在原节点上完成。

易错点总结

[!yellow]

• 覆盖 next 之后才保存，会把原后继丢掉。
• 尚未走到分支末尾就弹栈，会截断子链。
• 只连接正向指针或不清 child，结果仍不符合单层双向结构。

相似题目

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

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2023/28665344

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