430. Flatten a Multilevel Doubly Linked List

class Solution {
    public Node flatten(Node head) {
        flattenAndReturnTail(head);
        return head;
    }

    private Node flattenAndReturnTail(Node head) {
        Node curr = head, tail = head;
        while (curr != null) {
            tail = curr;
            if (curr.child != null) {
                Node next = curr.next;
                curr.next = curr.child;
                curr.child.prev = curr;
                Node childTail = flattenAndReturnTail(curr.child);
                curr.child = null;
                childTail.next = next;
                if (next != null) { // 注意此处判空
                    next.prev = childTail;
                }
                curr = childTail; // 跳过子链表，提高效率，但同时要记录子链表的最后一个节点，所以此处不能直接跳至 next
            } else {
                curr = curr.next;
            }
        }

        return tail;
    }
}

注意此题是双向链表，需要同时处理前后指针。

References

430. Flatten a Multilevel Doubly Linked List
剑指 Offer II 028. 展平多级双向链表