侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【递归, DFS】扁平化多级双向链表

GabrielxD
2022-06-10 / 0 评论 / 0 点赞 / 25 阅读 / 1,366 字 / 正在检测是否收录...

题目

430. 扁平化多级双向链表


你会得到一个双链表,其中包含的节点有一个下一个指针、一个前一个指针和一个额外的 子指针 。这个子指针可能指向一个单独的双向链表,也包含这些特殊的节点。这些子列表可以有一个或多个自己的子列表,以此类推,以生成如下面的示例所示的 多层数据结构

给定链表的头节点 head ,将链表 扁平化 ,以便所有节点都出现在单层双链表中。让 curr 是一个带有子列表的节点。子列表中的节点应该出现在扁平化列表中的 curr 之后curr.next 之前

返回 扁平列表的 head 。列表中的节点必须将其 所有 子指针设置为 null

示例 1:

image-20220610001541016

输入:head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
输出:[1,2,3,7,8,11,12,9,10,4,5,6]
解释:输入的多级列表如上图所示。
扁平化后的链表如下图:

image-20220610001551067

示例 2:

image-20220610001556973

输入:head = [1,2,null,3]
输出:[1,3,2]
解释:输入的多级列表如上图所示。
扁平化后的链表如下图:

image-20220610001604192

示例 3:

输入:head = []
输出:[]
说明:输入中可能存在空列表。

提示:

  • 节点数目不超过 1000
  • 1 <= Node.val <= 105

如何表示测试用例中的多级链表?

示例 1 为例:

 1---2---3---4---5---6--NULL
         |
         7---8---9---10--NULL
             |
             11--12--NULL

序列化其中的每一级之后:

[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]

为了将每一级都序列化到一起,我们需要每一级中添加值为 null 的元素,以表示没有节点连接到上一级的上级节点。

[1,2,3,4,5,6,null]
[null,null,7,8,9,10,null]
[null,11,12,null]

合并所有序列化结果,并去除末尾的 null 。

[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

解题

方法一:DFS 递归

思路

新建一个 curr 节点复制为头节点的引用,遍历主链表中的每个节点:

  • 记录 curr 当前的后继节点(next)
  • 如果当前节点有子链表
    • 递归地扁平化子链表,拿到子链表的头节点(childHead)
    • 把当前节点的后继结点置为子链表的头节点
    • 子链表的头节点前驱结点置为当前节点
    • 把当前节点的子链表置为空
    • 迭代找到子链表的尾节点 (可以从 childHead 开始找,也可以从 curr 开始找,因为 curr 的后继结点已经被置为 childHead)
    • 子链表的尾节点后继结点置为原后继结点(next)
    • 如果当前节点不是尾节点的话 (还有后继结点),把原后继结点的前驱节点置为子链表的尾节点
  • 把当前节点置为之前记下的原后继结点(next)

最后返回头节点即可。

代码

class Solution {
    public Node flatten(Node head) {
        Node curr = head;
        while (curr != null) {
            Node next = curr.next;
            if (curr.child != null) {
                Node childHead = flatten(curr.child);
                curr.next = childHead;
                childHead.prev = curr;
                curr.child = null;
                Node childTail = childHead;
                while (childTail.next != null) childTail = childTail.next;
                childTail.next = next;
                if (next != null) next.prev = childTail;
            }
            curr = next;
        }
        return head;
    }
}

优化: 处理子链表时同时返回头尾节点

在上面可以发现,递归扁平化子链表时迭代到了子链表的尾节点(childTail),但在后面链接 nextchildTail 时又迭代找了一次 childTail,浪费了时间,所以可以用一个新方法 flattenDFS 返回值是扁平化链表头尾节点组成的数组(headAndTail)。

class Solution {
    public Node flatten(Node head) {
        flattenDFS(head);
        return head;
    }

    private Node[] flattenDFS(Node head) {
        Node curr = head, tail = curr;
        while (curr != null) {
            Node next = curr.next;
            if (curr.child != null) {
                Node[] childHeadAndTail = flattenDFS(curr.child);
                Node childHead = childHeadAndTail[0], childTail = childHeadAndTail[1];
                curr.next = childHead;
                childHead.prev = curr;
                curr.child = null;
                curr = childTail;
                curr.next = next;
                if (next != null) next.prev = curr;
            }
            if (next == null) tail = curr;
            curr = next;
        }
        return new Node[]{head, tail};
    }
}

优化: 处理子链表时返回尾节点

子链表的头节点可以不用返回,直接通过 curr.child 就可以拿到,上面同时返回头尾节点浪费空间,所以新方法 flattenDFS 只返回扁平化链表的尾节点即可。

class Solution {
    public Node flatten(Node head) {
        flattenDFS(head);
        return head;
    }

    private Node flattenDFS(Node head) {
        Node curr = head, tail = curr;
        while (curr != null) {
            Node next = curr.next;
            if (curr.child != null) {
                Node childTail = flattenDFS(curr.child);
                curr.next = curr.child;
                curr.child.prev = curr;
                curr.child = null;
                curr = childTail;
                curr.next = next;
                if (next != null) next.prev = curr;
            }
            if (next == null) tail = curr;
            curr = next;
        }
        return tail;
    }
}

方法二:迭代

思路

与递归的思路基本一致,但是每次只能处理一层子链表,所以不能跳过被处理过拼接后的子链表,应该接着子链表继续向后遍历

代码

class Solution {
    public Node flatten(Node head) {
        // 如果当前 curr 有子链表, 处理完后 curr.next 会变成子链表的头节点
        // 也就是不会跳过处理后的子链表, 而是接下去遍历
        for (Node curr = head; curr != null; curr = curr.next) {
            Node next = curr.next;
            if (curr.child != null) {
                curr.next = curr.child;
                curr.child.prev = curr;
                curr.child = null;
                Node tail = curr;
                while (tail.next != null) tail = tail.next;
                tail.next = next;
                if (next != null) next.prev = tail;
            }
        }
        return head;
    }
}
0

评论区