/*// Definition for a Node.class Node {public:    int val = NULL;    Node* prev = NULL;    Node* next = NULL;    Node* child = NULL;    Node() {}    Node(int _val, Node* _prev, Node* _next, Node* _child) {        val = _val;        prev = _prev;        next = _next;        child = _child;    }};*/class Solution {public:    Node* flatten(Node* head) {        if (head == NULL)   return head;        flatten2(head);        return head;    }    Node* flatten2(Node* head) {    // flatten and return tail        Node* ret = head;        while (head) {            ret = head;            if (head->child) {                Node* tail = flatten2(head->child);                tail->next = head->next;                if (tail->next)                    tail->next->prev = tail;                head->next = head->child;                head->next->prev = head;                head->child = NULL;                head = tail->next;                ret = tail;            }            else {                head = head->next;            }        }        return ret;    }};