1.题目基本信息

1.1.题目描述

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

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

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

1.2.题目地址

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

2.解题方法

2.1.解题思路

深度优先搜索（关键是准确对递归函数的定义）

3.解题代码

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: 'Optional[Node]') -> 'Optional[Node]':
        # 递归任务：将以node开头的链表进行扁平化，并返回尾结点
        @cache
        def dfs(node:Node) -> Node:
            cur = node
            last = None
            while cur is not None:
                curNext = cur.next
                if cur.child:
                    rear = dfs(cur.child)
                    cur.next = cur.child
                    cur.next.prev = cur
                    if curNext:
                        rear.next = curNext
                        curNext.prev = rear
                    cur.child = None
                    last = rear
                else:
                    last = cur
                cur = curNext
            return last
        dfs(head)
        return head

c++代码

/*
// 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 = NULL;
        while (cur != NULL) {
            Node* curNext = cur -> next;
            if (cur -> child) {
                Node* rear = dfs(cur -> child);
                cur -> next = cur -> child;
                cur -> next -> prev = cur;
                if (curNext) {
                    rear -> next = curNext;
                    curNext -> prev = rear;
                }
                cur -> child = NULL;
                last = rear;
            } else {
                last = cur;
            }
            cur = curNext;
        }
        return last;
    }

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

4.执行结果