当前位置: 首页 > news >正文

阜宁县住房与城乡建设局网站ueeshop建站费用

阜宁县住房与城乡建设局网站,ueeshop建站费用,电动工具咋在网上做网站,物联网小项目原题链接 难度:middle\color{orange}{middle}middle 题目描述 你会得到一个双链表,其中包含的节点有一个下一个指针、一个前一个指针和一个额外的 子指针 。这个子指针可能指向一个单独的双向链表,也包含这些特殊的节点。这些子列表可以有一…

原题链接

难度:middle\color{orange}{middle}middle


题目描述

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

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

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

示例 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]
解释:输入的多级列表如上图所示。
扁平化后的链表如下图:

示例 2:

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

示例 3:

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

提示:

  • 节点数目不超过 100010001000
  • 1<=Node.val<=1051 <= Node.val <= 10^{5}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]

算法

(递归) O(n)O(n)O(n)

  1. 定义 flat 函数,参数为当前级链表的头结点,返回当前级链表扁平化后的最后一个结点。
  2. flat 函数中,从头结点开始遍历,遍历的节点可分为四类:
    • 第一类:既没有孩子节点也没有后驱节点,说明说明已经是该层最后一个节点了,直接返回该节点。

    • 第二类:没有孩子节点,只有后驱节点。更新 head,让 head = head->next

    • 第三类:既有孩子节点也有后驱节点:

      • 则用临时变量 nxt 记录下当前结点的 childnext,然后递归调用 flat(head->child),用临时变量 tail 记录调用的返回值。
      • 递归结束后,需要修改当前结点 curchildnext,以及 child 结点的 prev。修改 tailnext。如果 nxt 不为空,则修改 nxtprevtail
      • 最后移动当前结点 curhead
    • 第四类:只有孩子节点,没有后驱节点。那么只需要将孩子节点变成后驱节点就可以了

复杂度分析

  • 时间复杂度:每个结点仅遍历一次,故时间复杂度为 O(n)O(n)O(n)

  • 空间复杂度 : 递归需要系统栈空间,故空间复杂度为链表的最大级数。

C++ 代码

/*
// Definition for a Node.
class Node {
public:int val;Node* prev;Node* next;Node* child;
};
*/class Solution {
public:// flat 函数返回当前级链表扁平化后的最后一个结点Node* flat(Node* head) {while (head) {//既没有孩子节点也没有后驱节点,说明已经是该层最后一个节点了,如6,10,12。直接返回该节点if (!head->child && !head->next) return head;//如果没有孩子节点,只有后驱节点。如1,2,4,5,7,9,11,更新headelse if (!head->child) head = head->next;//既有孩子节点也有后驱节点else if (head->next) {//先将孩子链表扁平化并返回末尾节点。Node* tail = flat(head->child);Node* nxt = head->next;tail->next = nxt;head->next = head->child;//将扁平化的链表插入当前节点的后面,注意是双向链表,并且孩子节点需要变成NULLif (tail->next) tail->next->prev = tail;if (head->next) head->next->prev = head;head->child = NULL;//更新当前节点head = tail->next;} else {//只有孩子节点,没有后驱节点。那么只需要将孩子节点变成后驱节点就可以了head->next = head->child;head->next->prev = head;head->child = NULL;head = head->next;}}return head;}Node* flatten(Node* head) {flat(head);return head;}
};
http://www.khdw.cn/news/61634.html

相关文章:

  • 柳州微网站开发厦门网络关键词排名
  • 全球包装设计网天津seo诊断
  • 给你一个网站你如何做优化网页设计师
  • 网页网站设计价格澎湃新闻
  • java学完后可以做网站吗小说风云榜
  • 北京网站建设的公司渠道策略的四种方式
  • 做网站要会写什么搜索引擎营销优缺点
  • 百度采购网玉溪seo
  • 专教做美食的网站江苏搜索引擎优化公司
  • 论坛网站怎么推广3天网站seo优化成为超级品牌
  • thinkphp集成wordpress网站优化及推广方案
  • 电商网页设计流程重庆网络seo
  • 旅游网站建设项目策划书新品牌推广策划方案
  • 做网站用到java吗百度的总部在哪里
  • 潍坊网站建设套餐济南网站制作
  • 三好街做网站公司seo推广具体做什么
  • 杭州做网站hzyze最新新闻事件摘抄
  • vue做pc网站衡阳百度seo
  • 贵阳网站开发公司推荐网络推广营销方法
  • 在线教育网站平台建设的意义网站建设模板
  • 国外做爰网站龙华百度快速排名
  • 南宁建站服务公司企业关键词排名优化哪家好
  • nba最新排名情况郑州seo线上推广技术
  • 如何建设机器人教育网站宜昌网站建设公司
  • 免费学校网站模板网站建设与维护
  • 个人网站需求分析营销推广活动方案
  • 营销策划包括哪几个方面班级优化大师的利和弊
  • 网络推广商城网站怎样推广app
  • 使用oss图片做网站广告优化师培训
  • 漯河做网站哪家好seo长尾关键词优化