430. Flatten a Multilevel Doubly Linked List

recursive O(n) time

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

    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) {
        Node dummy_head;
        dummy_head.next = head;
        helper(head);
        return dummy_head.next;
    }

    Node *helper(Node *head) { // 返回处理以后的最后一个非空node
        if (!head) return head;
        if (head->child) {
            auto succ = head->next;
            head->next = head->child;
            head->child = nullptr;
            head->next->prev = head;
            auto prev = helper(head->next);
            prev->next = succ;
            if (succ) {
                succ->prev = prev;
            }
        }
        return head->next ? helper(head->next) : head;
    }
};

iterative O(n) time
每个node访问两次

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

    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) {
        for (auto p = head; p; p = p->next) {
            if (p->child) {
                auto succ = p->next;
                p->next = p->child;
                p->next->prev = p;
                p->child = nullptr;
                auto tail = p->next;
                while (tail->next) { // 找到最后一个节点跟上一层断点连上
                    tail = tail->next;
                }
                tail->next = succ;
                if (succ) {
                    succ->prev = tail;
                }
            }
        }
        return head;
    }
};