题目链接

剑指 Offer II 028. 展平多级双向链表 mid

题目描述

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

给定位于列表第一级的头节点，请扁平化列表，即将这样的多级双向链表展平成普通的双向链表，使所有结点出现在单级双链表中。

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

输入的多级列表如下图所示：

1—2—NULL
|
3—NULL

示例 3：

输入：head = []
输出：[]

提示：

• 节点数目不超过 1000
• $1<=Node.val<=10^5$

解法 ： dfs

类似于 树的前序遍历。

我们用 pre来记录当前结点 root的前驱结点，用 nextNode来记录当前结点 root的后继结点。

如果 pre不为空，就让前驱结点pre的后继指针指向 root，即 pre.next = root。

当前结点root的前驱指针直接指向 pre，即 root.prev = pre。

接着再让 pre变为当前结点，先递归处理当前结点的子结点 root.child（如果 root.child != null的情况下），处理完毕之后，将root.child置为空，即 root.child = null表明其处理完毕，接着再递归处理下一个结点 nextNode。

时间复杂度： $O(n)$ $n$是结点的数量

C++代码：

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

class Solution {
public:
    Node * pre = nullptr;

    void dfs(Node * root){
        if(root == nullptr) return;

        if(pre != nullptr) pre->next = root;
        Node * nextNode = root->next;
        
        root->prev = pre;
        pre = root;

        dfs(root->child);
        root->child = nullptr;
        dfs(nextNode);
    }

    Node* flatten(Node* head) {
        dfs(head);
        return head;
    }
};

Python代码：

"""
# Definition for a Node.
class Node:
    def __init__(self, val, prev, next, child):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child
"""

class Solution:      
    def flatten(self, head: 'Node') -> 'Node':
        pre = None
        def dfs(root : 'Node') -> 'void':
            if root == None:
                return
            nonlocal pre

            if pre != None:
                pre.next = root
            root.prev = pre

            nextNode = root.next
            pre = root
            
            dfs(root.child)
            root.child = None
            dfs(nextNode)
        
        dfs(head)
        return head