面试算法28:展平多级双向链表

这篇具有很好参考价值的文章主要介绍了面试算法28:展平多级双向链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

问题

在一个多级双向链表中,节点除了有两个指针分别指向前后两个节点,还有一个指针指向它的子链表,并且子链表也是一个双向链表,它的节点也有指向子链表的指针。请将这样的多级双向链表展平成普通的双向链表,即所有节点都没有子链表。

面试算法28:展平多级双向链表,算法,面试,算法,链表

分析

在面试时如果遇到这种类型的题目,应聘者需要先弄清楚展平的规则。在图4.14的示例中,节点2有一个子链表,展平之后该子链表插入节点2和它的下一个节点3之间。节点6也有一个子链表,展平之后该子链表插入节点6和它的下一个节点7之间。由此可知,展平的规则是一个节点的子链展平之后将插入该节点和它的下一个节点之间。

由于子链表中的节点也可能有子链表,因此这里的链表是一个递归的结构。在展平子链表时,如果它也有自己的子链表,那么它嵌套的子链表也要一起展平。嵌套子链表和外层子链表的结构类似,可以用同样的方法展平,因此可以用递归函数来展平链表。文章来源地址https://www.toymoban.com/news/detail-724083.html

public class Test {
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        Node node9 = new Node(9);

        node1.next = node2;
        node2.prev = node1;
        node2.child = node5;
        node2.next = node3;
        node3.prev = node2;
        node3.next = node4;
        node4.prev = node3;
        node5.next = node6;
        node6.prev = node5;
        node6.child = node8;
        node6.next = node7;
        node7.prev = node6;
        node8.next = node9;
        node9.prev = node8;

        Node result = flatten(node1);
        while (result != null) {
            System.out.println(result.val);
            result = result.next;
        }
    }

    public static Node flatten(Node head) {
        flattenGetTail(head);
        return head;
    }

    private static Node flattenGetTail(Node head) {
        Node node = head;
        Node tail = null;
        while (node != null) {
            Node next = node.next;
            if (node.child != null) {
                Node child = node.child;
                Node childTail = flattenGetTail(node.child);

                node.child = null;
                node.next = child;
                child.prev = node;
                childTail.next = next;
                if (next != null) {
                    next.prev = childTail;
                }

                tail = childTail;
            }
            else {
                tail = node;
            }

            node = next;
        }

        return tail;
    }
}

到了这里,关于面试算法28:展平多级双向链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构与算法(四):双向链表

    双向链表概念和单向链表是一致的,区别在于双向链表在单向链表的基础上,指针区域多了一个指向上一个节点的指针。单向链表内容可以参考我的上一篇文章:http://t.csdn.cn/Iu56H。 基本的数据结构如图所示: 双向链表结构包含了节点的数据内容和两个指针:指向前一个节点

    2024年02月14日
    浏览(52)
  • 【数据结构与算法】之双向链表及其实现!

    ​                                                                                 个人主页:秋风起,再归来~                                                                                             数据结构与

    2024年04月23日
    浏览(42)
  • 算法竞赛基础:C++双向链表的结构和实现(普通链表、List、静态链表)

    本文将会介绍在算法竞赛中双向链表的几种使用方式,适合有一定基础的人阅读。 一般来说,普通的链表结构是这样的: next指针指向下一个链表,这样的结构只能够支持单向查询。 双向链表,顾名思义,就是可以支持双向的访问和查询。 也就是这样的: 这种链表为访问前

    2024年01月24日
    浏览(42)
  • 【数据结构与算法】 - 双向链表 - 详细实现思路及代码

    前几篇文章介绍了怎样去实现单链表、单循环链表, 这篇文章主要介绍 双向链表 以及实现双向链表的步骤,最后提供我自己根据理解实现双向链表的C语言代码 。跟着后面实现思路看下去,应该可以看懂代码,看懂代码后,就对双向链表有了比较抽象的理解了,最后自己再

    2024年02月01日
    浏览(39)
  • 算法村第一关黄铜|链表|单链表与双向链表(c语言&c++实现)

    1.理解C 语言里是如何构造出链表的 2.链表增加元素,首部、中间和尾部分别会有什么问题,该如何处理? 3.链表删除元素,首部、中间和尾部分别会有什么问题,该如何处理? 4.双向链表是如何构造的,如何实现元素的插入和删除。 链表是一种常见的数据结构,由一系列节

    2024年02月15日
    浏览(39)
  • 【数据结构和算法】使用数组的结构实现链表(单向或双向)

    上文我们通过结构体的结构实现了队列 、以及循环队列的实现,我们或许在其他老师的教学中,只学到了用结构体的形式来实现链表、队列、栈等数据结构,本文我想告诉你的是,我们 可以使用数组的结构实现链表、单调栈、单调队列 目录 前言 一、用数组结构的好处 1.数

    2024年01月20日
    浏览(74)
  • 【数据结构和算法】实现带头双向循环链表(最复杂的链表)

    前文,我们实现了认识了链表这一结构,并实现了无头单向非循环链表,接下来我们实现另一种常用的链表结构,带头双向循环链表。如有仍不了解单向链表的,请看这一篇文章(7条消息) 【数据结构和算法】认识线性表中的链表,并实现单向链表_小王学代码的博客-CSDN博客

    2024年01月17日
    浏览(78)
  • 【数据结构与算法】4、双向链表(学习 jdk 的 LinkedList 部分源码)

    🎁 单链表的节点中只有一个 next 指针引用着下一个节点的地址 🎁 当要获取单链表中的最后一个元素的时候,需要从头节点开始遍历到最后 🎁 单链表一开始的时候有 first 头指针引用着头节点的地址 💰 双向链表可以提升链表的综合性能 💰 双向链表的节点中有 prev 指针引

    2024年02月12日
    浏览(46)
  • 数据结构课程设计题目——链表综合算法设计、带头双向循环链表、插入、显示、删除、修改、排序

      课程设计题目1–链表综合算法设计   一、设计内容   已知简单的人事信息系统中职工记录包含职工编号(no)、职工姓名(name)、部门名称(depname)、职称(title)和工资数(salary)等信息(可以增加其他信息),设计并完成一个简单的人事信息管理系统,要求完成但不

    2024年02月08日
    浏览(64)
  • 【Day28】力扣算法(超详细思路+注释) [1790. 仅执行一次字符串交换能否使两个字符串相等 ] [328. 奇偶链表 ][148. 排序链表]

    原题链接:1790. 仅执行一次字符串交换能否使两个字符串相等 题目描述 : 给你长度相等的两个字符串 s1 和 s2 。一次 字符串交换操作的步骤如下:选出某个字符串中的两个下标(不必不同),并交换这两个下标所对应的字符。 如果对 其中一个字符串 执行 最多一次字符串交

    2024年01月22日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包