☕ DSA Java Articles

Topics › Linked List › Hard Problems of LL

Flattening of LL

Hard TUF ID 2841 A2Z

Java source ↗ Edit this article ↗

Problem

You are given a linked list in which every node has two pointers: next, which links the nodes of the top-level list, and bottom, which links a vertical sub-list hanging below that node. Each vertical list (including its top node) is sorted in ascending order through bottom pointers. Flatten the structure into a single list that is sorted in ascending order and linked only through bottom pointers; every next pointer in the result must be null. Return the head of the flattened list.

Constraints: 0 ≤ k ≤ 10^4 top-level nodes, total node count N ≤ 10^5, values fit in an int. The top-level nodes themselves are not necessarily sorted among each other, although in the classic statement they are.

Example 1

5 -> 10 -> 19 -> 28
|    |     |     |
7    20    22    35
|          |     |
8          50    40
|                |
30               45

answer = 5 -> 7 -> 8 -> 10 -> 19 -> 20 -> 22 -> 28 -> 30 -> 35 -> 40 -> 45 -> 50   (through bottom)

Example 2

5 -> 10 -> 19 -> 28          // every column has a single node
answer = 5 -> 10 -> 19 -> 28

Example 3

1                            // a single column is already flat
|
2
|
3
answer = 1 -> 2 -> 3

The structure is really k sorted lists, so the problem is a disguised merge k sorted lists. Everything below follows from that observation.

Approach 1: Brute force, collect and sort

Intuition. Ignore the sorted columns entirely. Visit every node (walk next across the top, bottom down each column), gather all values, sort them, and build a brand-new chain of nodes linked through bottom. It is correct for any input, even unsorted columns, which is also a hint that it is doing more work than necessary.

Algorithm.

  1. For each top-level node, walk its column via bottom and add every value to a list.
  2. Sort the list.
  3. Create a new node for each value, linking them through bottom behind a dummy node.
  4. Return dummy.bottom.
static Node bruteForce(Node head) {
    List<Integer> vals = new ArrayList<>();
    for (Node col = head; col != null; col = col.next) {
        for (Node t = col; t != null; t = t.bottom) vals.add(t.val);
    }
    Collections.sort(vals);
    Node dummy = new Node(0), tail = dummy;
    for (int v : vals) { tail.bottom = new Node(v); tail = tail.bottom; }
    return dummy.bottom;
}

Complexity. Time O(N log N) for the sort over all N nodes. Space O(N) for the value list and the new nodes.

The sorting step throws away the fact that each column is already sorted. Merging sorted sequences is cheaper than sorting from scratch, and the problem expects the original nodes to be reused rather than copied.

Approach 2: Better, merge the columns one at a time

Intuition. Two sorted lists can be merged into one sorted list in linear time, exactly as in merge sort. If the columns to the right of the current one have already been flattened into a single sorted list, we only need to merge the current column into it. Recursion expresses this directly: flatten everything from head.next onward, then merge head’s column with that result. The recursion bottoms out at the last column, which is already a sorted bottom list.

Algorithm.

  1. If head is null or has no next, return head.
  2. Let rest = better(head.next), the flattened version of all columns to the right.
  3. Set head.next = null so this column no longer points sideways.
  4. Return mergeBottom(head, rest).

The merge walks both lists, always attaching the smaller front node to the tail of the result and clearing its next pointer, then attaches whatever remains.

static Node better(Node head) {
    if (head == null || head.next == null) return head;        // a single column is already a sorted bottom list
    Node rest = better(head.next);                             // flatten columns 2..k first
    head.next = null;                                          // this column no longer points sideways
    return mergeBottom(head, rest);
}

static Node mergeBottom(Node a, Node b) {
    Node dummy = new Node(0), tail = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) { tail.bottom = a; a = a.bottom; }
        else { tail.bottom = b; b = b.bottom; }
        tail = tail.bottom;
        tail.next = null;                                      // keep the result strictly one-dimensional
    }
    tail.bottom = (a != null) ? a : b;                         // whatever is left is already sorted
    return dummy.bottom;
}

Complexity. Time O(N × k) in the worst case: the i-th merge from the right processes all nodes of columns i..k, so a node in the last column is touched once per merge. When all columns have similar length N/k, the total is about N/k × (1 + 2 + ... + k) = O(N × k). Space O(k) for the recursion stack; no new nodes are created.

This is the solution most often presented for the problem, and it is the right one to know: it reuses nodes, needs no auxiliary data structure, and the merge step is a standard tool. Its weakness is the repeated re-merging of the right-hand lists. With k = 10^4 columns of ten nodes each, the merges perform around 5 × 10^8 comparisons, which is borderline.

Approach 3: Optimal time, k-way merge with a min-heap

Intuition. Instead of merging lists pairwise, merge all of them at once. At any moment the next value of the output is the smallest of the current front nodes of the k columns. A min-heap keyed on node value gives us that smallest front in O(log k), and when we remove a node we push the node below it in the same column, so the heap always holds exactly one candidate per non-empty column. Each node enters and leaves the heap once.

Algorithm.

  1. Push every top-level node into a min-heap ordered by val.
  2. While the heap is not empty:
    • Pop the smallest node s. If s.bottom exists, push it.
    • Clear s.next, append s to the result through bottom, and make it the new tail.
  3. Set the final tail’s bottom to null and return dummy.bottom.
static Node optimal(Node head) {
    PriorityQueue<Node> heap = new PriorityQueue<>((x, y) -> Integer.compare(x.val, y.val));
    for (Node col = head; col != null; col = col.next) heap.offer(col);
    Node dummy = new Node(0), tail = dummy;
    while (!heap.isEmpty()) {
        Node smallest = heap.poll();
        if (smallest.bottom != null) heap.offer(smallest.bottom);   // the next node of the same column takes its place
        smallest.next = null;
        tail.bottom = smallest;
        tail = smallest;
    }
    tail.bottom = null;
    return dummy.bottom;
}

Dry run on the columns [5, 7, 8, 30], [10, 20], [19, 22, 50], [28, 35, 40, 45] (first few steps):

heap contents (by value) popped pushed
5, 10, 19, 28 5 7
7, 10, 19, 28 7 8
8, 10, 19, 28 8 30
10, 19, 28, 30 10 20
19, 20, 28, 30 19 22
20, 22, 28, 30 20 (column exhausted)

The output so far is 5 -> 7 -> 8 -> 10 -> 19 -> 20, and the heap never holds more than four nodes.

Complexity. Time O(N log k): N pops and at most N pushes, each O(log k) since the heap never exceeds k entries. Space O(k) for the heap; no new nodes.

The order of operations inside the loop matters. Appending to the result overwrites the bottom pointer of the previous tail, which was itself a popped node. That is safe only because every node’s bottom is read, and its successor pushed, at the moment the node is popped, before the pointer can be overwritten. Push first, then append.

Compared with Approach 2, this version is asymptotically faster whenever k is large (log k versus k per node) at the cost of O(k) heap memory instead of O(k) stack. For two or three columns the recursive merge is simpler and just as fast; for thousands of columns the heap is the better tool.

Edge cases and pitfalls