Flatten a Multilevel Doubly Linked List

1public Node flatten(Node head) {
2    if (head == null) return null;
3
4    Node curr = head;
5    while (curr != null) {
6        if (curr.child != null) {
7            // Save next and find child tail
8            Node next = curr.next;
9            Node child = curr.child;
10
11            // Find tail of child list
12            Node tail = child;
13            while (tail.next != null) {
14                tail = tail.next;
15            }
16
17            // Connect curr -> child
18            curr.next = child;
19            child.prev = curr;
20
21            // Connect tail -> next
22            if (next != null) {
23                tail.next = next;
24                next.prev = tail;
25            }
26
27            // Clear child pointer
28            curr.child = null;
29        }
30
31        curr = curr.next;
32    }
33
34    return head;
35}