LeetCode刷题--- 430. 扁平化多级双向链表(深度优先搜索)

简介: LeetCode刷题--- 430. 扁平化多级双向链表(深度优先搜索)



一、编程题:430. 扁平化多级双向链表(深度优先搜索)

1.题目描述

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

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

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

2.示例1:

输入: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]

解释:输入的多级列表如上图所示。

扁平化后的链表如下图:

3.示例2:

输入:head = [1,2,null,3]

输出:[1,3,2]

解释:输入的多级列表如上图所示。

扁平化后的链表如下图:

4.示例3:

输入:head = []

输出:[]

说明:输入中可能存在空列表。

5.提示:

  • 节点数目不超过 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]


二、解题思路

  本题总体思路还是很简单的,就是将多个

  这题采用双指针,本题主要关键点为:

  • 1.该怎么去移动这两个指针?这一点要理清楚。这里双指针移动就比较简单了,分别向下移动一步即可;
  • 2.本题中两个指针分别指向链表当前节点和子节点的尾节点,然后尾节点(子节点的)链接在当前节点后并将当前节点的子节点置为空;
  • 3.在遍历过程中,需要不断维护这两个节点;

1.思路

解决方法1(个人想法):

  • Step 1.创建指针temp指向链表中头节点heap,tempChlid用于指向当前节点的子节点,初始值为null;
  • Step 2.当temp存在子节点时,tempChlid = temp.chlid,找到tempChlid的尾节点,然后将子节点的链表插入到当前节点temp后即可;
  • Step 3.重复2步骤,直到temp为null时循环终止,并返回链表头节点;

看不懂解释的话,直接看算法图解比较容易理解点

2.复杂度分析:

时间复杂度:每个节点被访问的次数仍为常数次,复杂度为O(n)。

空间复杂度:O(1)。我们只需要常数的空间存放若干变量。

3.算法图解

链表初始状态(注:本人不会做成流程动画,希望会的朋友可以私信我指点一二,说个软件名字也可以,谢谢

链表遍历过程

红色部分代表遍历到链表有子节点的节点,灰色部分代表子节点列表的尾节点


三、代码实现

每个代码块都写了注释,方便理解,代码还可以改进;

class Solution {
    public Node flatten(Node head) {
        Node temp = head, tempChlid;
        while(temp != null){
            // temp.child =null;
            
            // 当前节点存在子节点时,对子节点链表进行处理;
            if(temp.child != null){
                tempChlid = temp.child;
                
                // 找到链表尾节点
                while(tempChlid.next != null){
                    tempChlid = tempChlid.next;
                }
                // 调试专用
                // System.out.println("chilid.val = " + temp.child.val + " tempChlid.val = " + tempChlid.val);
                // 将上一级节点的后继节点拼接在子节点的链表尾节点后面
                tempChlid.next = temp.next;
                // 如果上一级节点的后继节点不为空的话,该后继节点的前驱节点指向子节点链表的尾节点
                if(temp.next != null) temp.next.prev = tempChlid;
                // 连接之后子节点的前驱节点指向当前节点,当前节点后继节点为子节点
                temp.next = temp.child; 
                temp.child.prev = temp;
                
            }
            // System.out.println("temp.val = " + temp.val);
            // 处理该节点的子节点之后,可将子节点指针置为空,同时将当前指针往后移下一位
            temp.child = null;
            temp = temp.next;
        }
        return head;
    }
}

提交结果:


总结

以上就是今天要讲的内容,这一题还是比较简单的,一看到这题的时候就立马想到同时遍历两个链表,然后把其中一个链表当做返回参数,让第二个链表的节点往里面插入即可。

感谢观看,如果有帮助到你,请给题解点个赞和收藏,让更多的人看到。🌹 🌹 🌹

也欢迎你,关注我。👍 👍 👍

原创不易,还希望各位大佬支持一下,你们的点赞、收藏和留言对我真的很重要!!!💕 💕 💕 最后,本文仍有许多不足之处,欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正!


相关文章
|
2天前
LeetCode链表hard 有思路?但写不出来?
LeetCode链表hard 有思路?但写不出来?
|
3天前
|
索引
每日一题:力扣328. 奇偶链表
每日一题:力扣328. 奇偶链表
13 4
|
3天前
|
算法 C++
【刷题】Leetcode 1609.奇偶树
这道题是我目前做过最难的题,虽然没有一遍做出来,但是参考大佬的代码,慢慢啃的感觉的真的很好。刷题继续!!!!!!
9 0
|
3天前
|
算法 索引
【刷题】滑动窗口精通 — Leetcode 30. 串联所有单词的子串 | Leetcode 76. 最小覆盖子串
经过这两道题目的书写,相信大家一定深刻认识到了滑动窗口的使用方法!!! 下面请大家继续刷题吧!!!
12 0
|
3天前
|
算法
【刷题】 leetcode 面试题 08.05.递归乘法
递归算法是一种在计算机科学和数学中广泛应用的解决问题的方法,其基本思想是利用问题的自我相似性,即将一个大问题分解为一个或多个相同或相似的小问题来解决。递归算法的核心在于函数(或过程)能够直接或间接地调用自身来求解问题的不同部分,直到达到基本情况(也称为基础案例或终止条件),这时可以直接得出答案而不必再进行递归调用。
25 4
【刷题】 leetcode 面试题 08.05.递归乘法
|
3天前
|
存储 算法 安全
【刷题】 leetcode 面试题 01.06 字符串压缩
来看效果: 非常好!!!过啦!!!
25 5
【刷题】 leetcode 面试题 01.06 字符串压缩
|
3天前
|
算法
LeetCode刷题---19. 删除链表的倒数第 N 个结点(双指针-快慢指针)
LeetCode刷题---19. 删除链表的倒数第 N 个结点(双指针-快慢指针)
|
3天前
|
存储
LeetCode刷题---817. 链表组件(哈希表)
LeetCode刷题---817. 链表组件(哈希表)
|
3天前
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解