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

冷不防 2023-03-13 05:24 13阅读 0赞

# 扁平化多级双向链表 #

## 一、LeetCode题解 ##

#### 瞧一瞧（求star!） ####

*  LeetCode题解Javascript版本：[Gitbook版本传送门][Gitbook]
 *  LeetCode题解Javascript版本：[CSDN传送门][CSDN]
 *  前端进阶笔记：[Gitbook传送门][Gitbook 1]

## 二、算法题 ##

### 题目 ###

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

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

示例 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
    };

#### 结果 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2piajY1Njg4Mzl6_size_16_color_FFFFFF_t_70]

### 关于我 ###

*  **decs：** 19年毕业的前端开发一枚，沉迷Js
 *  **E-mail：** webbj97@163.com
 *  **个人博客：** [CSDN][CSDN 1]
 *  **GitHub：** [传送门][Link 1]

[Gitbook]: https://webbj97.github.io/leetCode-Js/
[CSDN]: https://blog.csdn.net/jbj6568839z/article/details/103808459
[Gitbook 1]: https://webbj97.github.io/summary/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2piajY1Njg4Mzl6_size_16_color_FFFFFF_t_70]: /images/20230312/d5da12bad8924e44890910b0e8f337af.png
[CSDN 1]: https://blog.csdn.net/jbj6568839z
[Link 1]: https://github.com/webbj97