欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode题解:430.扁平化多级双向链表

程序员文章站 2022-04-24 15:33:46
...

扁平化多级双向链表

一、LeetCode题解

瞧一瞧(求star!)

二、算法题

题目

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

给你位于列表第一级的头节点,请你扁平化列表,使所有结点出现在单级双链表中。

示例 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]
解释:

这是链表的结构,向下为child节点
 1---2---3---4---5---6--NULL
         |
         7---8---9---10--NULL
             |
             11--12--NULL

解法一 (栈)

思路

  • 一个节点同时拥有child和next节点时,我们叫他spec节点
  • 保存spec节点的next节点。利用栈,压入栈中
  • 用child节点覆盖next节点。
  • 向下遍历节点
  • 最后在链表尾部以此链接栈顶的节点。

代码

var flatten = function(head) {
    var cur = head
    var temp = [] // 存储栈
    while(cur && (cur.child || cur.next)) {
        if(cur.child){
            if(cur.next){ // 不保存尾节点
                temp.push(cur.next)
            }
            cur.child.prev = cur // 维护prev节点
            cur.next = cur.child // child节点顶替next节点
            cur.child = null // 清空child节点(改变走向)
        }
        cur = cur.next // 向后一位
    }
    while(temp.length > 0){
        let node = temp.pop()
        node.prev = cur
        cur.next = node
        while(cur.next){ // 保证在尾节点链接
            cur = cur.next
        }
    }
    return head
};

结果

LeetCode题解:430.扁平化多级双向链表

关于我

  • decs: 19年毕业的前端开发一枚,沉迷Js
  • E-mail: aaa@qq.com
  • 个人博客: CSDN
  • GitHub: 传送门

上一篇: html

下一篇: Ugly Number II