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

Categories:

题目描述
思路分析
1. 解法一：栈模拟 DFS（推荐）
相似题目

题目描述

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

思路分析

解法一：栈模拟 DFS（推荐）

核心思路：

从头结点开始遍历，遇到 child 时先保存原 next 到栈中，再把 child 接到当前节点后面。

继续向前走，若链表走到尽头，则从栈中弹出之前保存的 next 接回。

过程中要断开 child 指针，保证链表最终扁平化。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数。

空间复杂度：O(n)，最坏情况下栈保存所有 next 指针。

import java.util.ArrayDeque;
import java.util.Deque;

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;
    }
}

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
}

相似题目

题目	难度	考察点
114. 二叉树展开为链表	中等	DFS + 链表
24. 两两交换链表中的节点	中等	链表指针
138. 复制带随机指针的链表	中等	链表指针
86. 分隔链表	中等	链表重排
92. 反转链表 II	中等	链表操作

本文作者: HGNULB

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