1.题目

题目地址(430. 扁平化多级双向链表 - 力扣（LeetCode）)

https://leetcode.cn/problems/flatten-a-multilevel-doubly-linked-list/

题目描述

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

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

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

示例 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 = []
输出：[]
说明：输入中可能存在空列表。

提示：

• 节点数目不超过 1000
• 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]

2.题解

2.1 DFS深度优先搜索

思路

由于每次有child子节点，我们优先遍历展开子节点到当前节点cur后，下一个节点next前(如果next存在), 我们很容易想到这是一个DFS深度优先搜索
1.返回条件
我们肯定要遍历完并展开当前层所有节点， 所以返回条件也就是 cur == nullptr;
2.执行操作

• 2.1 我们想要将子节点头部和当前节点cur构成双向链接很简单，我们交换一下next和prev即可
• 2.2 我们该如何将child子层节点尾部接到next呢？换言之，我们该如何获得该尾部节点呢？
  我们很容易发现当前层结束条件是cur == nullptr, cur遍历时必然会经过最后一个节点，那我们如果在之前用一个指针last保存住了该节点，然后作为返回值返回给上一层，就是可以直接获得子层的尾部节点了！
  我们可以每次去判断是不是最后一个节点再去用last保存,也可以在每次完成一次操作就更新一次last。
  这里的last有两种情况：
  1.如果当前节点cur没有节点，他自己cur就是最后一个；
  2.如果有子节点，那么就进行DFS深度优先搜索，找到子节点的末尾节点，该节点为展开后链表的尾节点

3.返回值
返回当前层的尾部节点， 便于上一层链接next

代码

• 语言支持：C++
  C++ Code:

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
};
*/

class Solution {
public:
    Node* DFS(Node* node) {
        Node* cur = node; 
        Node* last = nullptr; // 记录末尾位置
        while (cur != nullptr) {
            Node *next = cur->next; // 记录当前节点下一个节点位置
            // 如果当前节点存在子节点
            if(cur->child){
                Node *child_last = DFS(cur->child);
                cur->next = cur->child;
                cur->child->prev = cur;
                if(next != nullptr){
                    child_last->next = next;
                    next->prev = child_last;
                }
                // last = child_last;
                cur->child = nullptr;
                if(!cur->next) last = child_last;
            }else{
                // last = cur;
                if(!cur->next) last = cur;
            }
            cur = next;
        }
        return last;
    }
    Node* flatten(Node* head) {
        DFS(head);
        return head;
    }
};

复杂度分析

令 n 为数组长度。

• 时间复杂度：\(O(n)\)
• 空间复杂度：\(O(n)\)