Flatten a Linked List

The problem, simply

Every box has two arrows. next points right, to the next box in the top row. bottom points down, to the next box in its own column. Each column, read top to bottom, is sorted from small to big.

Turn the whole thing into one list that goes only through bottom arrows and is sorted. Return its first box. Here N is the total number of boxes and k is the number of columns.

A story to remember it

Picture it

Examples

Way 1: the simple way

Throw all the numbers in a basket, sort them, and build a new column.

1. Walk the top row with next. For each box, walk down its column with bottom and copy every number into a list.
2. Sort the list.
3. Build a new chain of boxes linked with bottom and return its head.

class Solution {
    Node flatten(Node root) {
        List<Integer> all = new ArrayList<>();
        for (Node col = root; col != null; col = col.next)
            for (Node p = col; p != null; p = p.bottom)
                all.add(p.data);                  // copy every number
        Collections.sort(all);

        Node dummy = new Node(0), tail = dummy;
        for (int v : all) {
            tail.bottom = new Node(v);            // new boxes, linked downwards
            tail = tail.bottom;
        }
        return dummy.bottom;
    }
}

How long it takes: copying is O(N) and sorting is O(N log N). Extra room: the copy and the new boxes, O(N). It ignores that every column is already sorted.

Way 2: the clever way

Every column is already sorted, so use the card pile trick: merging two sorted lists is easy and needs no extra room. Keep an answer, and merge each column into it, one after another.

1. The answer starts as the first column. Remember the next column, then cut the next arrow.
2. For each following column: merge the answer and the column through their bottom arrows. Two fingers, always take the smaller box, then glue on whatever is left.
3. Return the answer.

class Solution {
    Node flatten(Node root) {
        if (root == null) return null;
        Node answer = root;
        Node col = root.next;
        answer.next = null;
        while (col != null) {
            Node nextCol = col.next;       // remember the rest of the top row
            col.next = null;
            answer = merge(answer, col);   // merge one column into the answer
            col = nextCol;
        }
        return answer;
    }

    private Node merge(Node a, Node b) {
        Node dummy = new Node(0), tail = dummy;
        while (a != null && b != null) {
            if (a.data <= b.data) { tail.bottom = a; a = a.bottom; }
            else { tail.bottom = b; b = b.bottom; }
            tail = tail.bottom;
        }
        tail.bottom = (a != null) ? a : b;  // glue on the rest
        return dummy.bottom;
    }
}

How long it takes: the answer grows with every merge and is walked again each time. With k columns that is at most O(N k) steps. Extra room: a few fingers, O(1). The original boxes are reused, only arrows change.

Many solutions write the same thing with recursion: flatten everything to the right first, then merge this column with the result. That is the same work but uses O(k) stack.

Watch out for

• Losing the rest of the top row. Save col.next before you merge or change anything.
• Using < versus <= does not change correctness, but <= keeps equal values in their original order, which is nice.
• An empty input. Return null.
• Some judges print the answer through bottom only. Make sure the last box's bottom is null, which the merge's glue step gives you for free.

What interviewers ask next

• Can you make it faster? Yes. Merge the columns in pairs like a tournament, or use a min heap of the column tops. Both give O(N log k), the same as merging k sorted lists.
• Flatten a multilevel doubly linked list (LeetCode 430). There the child lists are not sorted and you splice them in place, in depth first order, instead of merging.
• Flatten a binary tree to a linked list. Again no sorting: put the left subtree between a node and its right subtree.
• Why does O(N k) happen? The first column gets walked in every merge. If columns are equal size, the work is about N k / 2.

Remember this

Grown-up words: the card piles are sorted linked lists, putting the smaller top card down is the merge step of merge sort, the top row is the next chain, the columns are bottom chains, and the tournament is divide and conquer merging.