专栏首页Michael阿明学习之路LeetCode 430. 扁平化多级双向链表(DFS)

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

1. 题目

您将获得一个双向链表,除了下一个和前一个指针之外,它还有一个子指针,可能指向单独的双向链表。这些子列表可能有一个或多个自己的子项,依此类推,生成多级数据结构,如下面的示例所示。

扁平化列表,使所有结点出现在单级双链表中。您将获得列表第一级的头部。

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

输出:
1-2-3-7-8-11-12-9-10-4-5-6-NULL

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/flatten-a-multilevel-doubly-linked-list 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. DFS

class Solution {
public:
    Node* flatten(Node* head) {
        Node *cur = head, *nextNode = NULL, *prevN = head;
        //所有的指针记得初始化,不要以为后面要付值就不要初始值,怕后面if没进去
        while(prevN)
        {	//遍历链表
            if(cur && cur->child) //当前有,且有子链
            {
                nextNode = cur->next;//记住上层cur后面的
                cur->next = flatten(cur->child);//展平
                cur->child->prev = cur;//子链头接上,展平
                cur->child = NULL;//将cur孩子删掉
            }
            prevN = cur;//prevnode移动
            if(cur)
                cur = cur->next;//cur移动
            if(!cur && nextNode)
            {	//当cur到终点的下一个时,且上层后面还有nextnode
                prevN->next = nextNode;//展平的终点prevN指向上层的nextnode
                nextNode->prev = prevN;//反向接上
                cur = prevN->next;//cur移动
                nextNode = NULL;//已接好,暂时没有child的需要展平,nextNode清空
            }
        }
        return head;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 1214. 查找两棵二叉搜索树之和(二叉树迭代器+双指针)

    给出两棵二叉搜索树,请你从两棵树中各找出一个节点,使得这两个节点的值之和等于目标值 Target。

    Michael阿明
  • LeetCode 450. 删除二叉搜索树中的节点

    Michael阿明
  • LeetCode 386. 字典序排数(DFS&循环)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/lexicographical-numbers 著作...

    Michael阿明
  • LeetCode 1214. 查找两棵二叉搜索树之和(二叉树迭代器+双指针)

    给出两棵二叉搜索树,请你从两棵树中各找出一个节点,使得这两个节点的值之和等于目标值 Target。

    Michael阿明
  • 暴力搜索------回溯法

    回溯法(backtracking)是深度优先搜索(DFS)的一种,按照深度优先的顺序便利解答树。应用范围很广,只要能把待求解的问题分成不太多的步骤,每个步骤又...

    刘开心_1266679
  • LeetCode 450. 删除二叉搜索树中的节点

    Michael阿明
  • 【剑指Offer】复杂链表的复制

    请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链...

    小新哟
  • 数据结构-静态链表及其插入删除操作

    什么是静态链表 我们平常提及的链表一般指的是动态链表,是使用指针将一个一个的结点连起来,除了动态链表之外,还有静态链表,这种链表用数组来描述,主要为了解决没有指...

    chaibubble
  • 圆圈中最后剩余的数字

    0,1,2,3 ,. . . ,n-1这n个数字排成一个圆圈,从数字0开始每次从这个圆圈里删除第m个数字,求这个圆圈里剩余的最后一个数字。

    大学里的混子
  • jsp中的警告:Attribute (cellpadding) is obsolete. Its use is discouraged in HTML5 documents.

    Attribute (width) is obsolete. Its use is discouraged in HTML5 documents. 属性(宽度)...

    黑泽君

扫码关注云+社区

领取腾讯云代金券