40-扁平化多级双向链表

自己的做法

算法思想

每一级链表中都只会有一个节点有下一级链表。也就是只有一个节点的child指针不为空。

使用递归思想。只需要考虑两级的链表。

递归参数：链表头节点； 输出：扁平化后的链表头节点，没有下一级链表。

递归终止条件：输入的链表的所有结点都没有子节点，即所有结点child指针都为空。这时直接返回头节点即可。

递归过程：

首先遍历链表，如果某一个节点的child节点不为空，即有下一级链表，设该节点为cur。

则递归调用，传入参数为cur->child，设child_head为递归调用的返回值。

child_head对应的链表已经扁平化。应将其插入cur和cur->next之间。

首先遍历child_head链表，找到尾节点child_node。然后进行插入，插入步骤：

1. 判断cur节点是否有下一个节点，如有，将cur的下一个节点的prev指针指向child_node
2. 将child_node的next指针指向cur->next。这时尾部插入结束。
3. 将child_head的prev指针指向cur
4. cur的next指针指向child_head
5. 最后，将cur的child指针置为空

子链表插入完成。

算法实现

class Solution {
public:
    Node* flatten(Node* head) {
        Node * cur = head;
        while (cur && cur->child == nullptr) {
            cur = cur->next;
        }
        if(cur == nullptr) {
            return head;
        }
        Node * child_head = flatten(cur->child);
        Node * child_node = child_head;
        while (child_node->next) {
            child_node = child_node->next;
        }
        if(cur->next) {
            cur->next->prev = child_node;
        }
        child_node->next = cur->next;
        child_head->prev = cur;
        cur->next = child_head;
        cur->child = nullptr;
        return head;

    }
};

这是我能做到的吗，我感觉匪夷所思啊。

性能分析

时间复杂度：$O(n)$，n为节点数。

空间复杂度：$O(n)$，n为节点数，因为可能每级链表都只有一个节点，那么每个节点都会有child节点。递归栈需要都保存

参考答案，笑死，根本看不懂。

用到了深度优先搜索，等我复习了再来看。