FlattenAMultiLevelDoublyLinkedList.java

// T: O(n)
// S: O(n)

public class FlattenAMultiLevelDoublyLinkedList {
    private static final class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;
    }

    public Node flatten(Node head) {
        for (Node temp = head ; temp != null ; temp = temp.next) {
            if (temp.child != null) {
                Node lastNodeOfFlattenedChildren = flattenLinkedList(temp.child);
                lastNodeOfFlattenedChildren.next = temp.next;
                if (temp.next != null) {
                    temp.next.prev = lastNodeOfFlattenedChildren;
                }
                temp.next = temp.child;
                temp.child.prev = temp;
                temp.child = null;
            }
        }
        return head;
    }

    private Node flattenLinkedList(Node head) {
        Node temp = head;
        for (; temp.next != null ; temp = temp.next) {
            if (temp.child != null) {
                Node lastNodeOfFlattenedChildren = flattenLinkedList(temp.child);
                lastNodeOfFlattenedChildren.next = temp.next;
                temp.next.prev = lastNodeOfFlattenedChildren;
                temp.next = temp.child;
                temp.child.prev = temp;
                temp.child = null;
            }
        }
        if (temp.child != null) {
            Node lastNodeOfFlattenedChildren = flattenLinkedList(temp.child);
            temp.next = temp.child;
            temp.child.prev = temp;
            temp.child = null;
            return lastNodeOfFlattenedChildren;
        }
        return temp;
    }
}