[数据结构与算法]剑指 Offer II 028. 展平多级双向链表

题目

力扣

思路 递归

起始时建立一个哨兵节点dummy指向head，防止空节点等边界问题。如果没有child节点，就让指针后移。如果有child节点，就把head.child传到flatten递归处理，得到处理后的节点chead。建立head与chead的相邻关系，继续往后处理，直到尾部，再建立原本的head->next与尾部节点的相邻关系。

代码

class Solution {
public:
    Node* flatten(Node* head) {
        Node* dummy=new Node();
        dummy->next=head;
        while(head){
            if(head->child==NULL)
                head=head->next;
            else if(head && head->child){
                Node* tmp=head->next;
                Node* chead=flatten(head->child);
                head->child=NULL;
                head->next=chead;
                chead->prev=head;
                while(head->next)
                    head=head->next;
                head->next=tmp;
                if(tmp)tmp->prev=head;
            }
        }
        return dummy->next;
    }
};