【Leetcode】430. 扁平化多级双向链表

一、题目

二、思路

2.1 解题思路

2.2 代码尝试

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

class Solution {
public:
    Node* flatten(Node* head) {
        //先递归找到最下面的子节点

        Node* p=head;
        p=child(p->child);

    }

    Node* child(Node* head){
        if(head->child){
            head=child(head->child);
            return head;
        }else{
            return head;
        }
        
    }

    Node* nex(Node* head){
        
    }
};

2.3 疑难问题

2.4 AI复盘

三、解法

class Solution {
public:
    Node* flatten(Node* head) {
        function<Node*(Node*)> dfs = [&](Node* node) {
            Node* cur = node;
            // 记录链表的最后一个节点
            Node* last = nullptr;

            while (cur) {
                Node* next = cur->next;
                //  如果有子节点，那么首先处理子节点
                if (cur->child) {
                    Node* child_last = dfs(cur->child);

                    next = cur->next;
                    //  将 node 与 child 相连
                    cur->next = cur->child;
                    cur->child->prev = cur;

                    //  如果 next 不为空，就将 last 与 next 相连
                    if (next) {
                        child_last->next = next;
                        next->prev = child_last;
                    }

                    // 将 child 置为空
                    cur->child = nullptr;
                    last = child_last;
                }
                else {
                    last = cur;
                }
                cur = next;
            }
            return last;
        };

        dfs(head);
        return head;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/flatten-a-multilevel-doubly-linked-list/solutions/1013884/bian-ping-hua-duo-ji-shuang-xiang-lian-b-383h/
来源：力扣（LeetCode）
着作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

四、收获

4.1 心得

需要找一个简单的题实现一下递归

4.2 举一反三