430. Flatten a Multilevel Doubly Linked List

Problem

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

Example1

Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Output: [1,2,3,7,8,11,12,9,10,4,5,6]
Explanation:

The multilevel linked list in the input is as follows:

After flattening the multilevel linked list it becomes:

Example2

Input: head = [1,2,null,3]
Output: [1,3,2]
Explanation:

The input multilevel linked list is as follows:

1—2---NULL
|
3—NULL

Example3

Input: head = []
Output: []

Solution

从头到尾遍历链表

• 如果当前节点有child，那么就递归将其child进行flatten，更新相关节点的prev和next后，将当前节点的child置为NULL，然后处理原始链表中当前节点的下一个节点
• 如果当前节点没有child，那么就处理下一个节点

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

class Solution {
public:
    Node* flatten(Node* head) {
        Node* cur = head;
        while(cur)
        {
            if(cur->child)
            {
                Node* flatten_child = flatten(cur->child);//将cur->child链表flatten
                Node* cur_child = flatten_child;//找到flatten后的cur->child链表的尾节点
                while(cur_child && cur_child->next)
                    cur_child = cur_child->next;
                
                Node* next = cur->next;
                cur->next = flatten_child; //更新当前节点的next
                flatten_child->prev = cur;//更新flatten后的cur->child链表的头节点的prev

                cur_child->next = next; //更新flatten后的cur->child链表的尾节点的next
                if(next)//如果存在cur->next，更新其prev
                    next->prev = cur_child;
                cur->child = NULL;//更新cur->child为null，去除multilevel

                cur = next;//跳到next
            }
            else
            {
                cur = cur->next;
            }
        }

        return head;
    }
};