☕ DSA Java Articles

Topics › Linked List › Hard Problems of LL

Flattening of LL

Hard TUF ID 612 SDE

Java source ↗ Edit this article ↗

Problem

You are given a two-level linked structure. Every node has two pointers:

Each vertical list is sorted in non-decreasing order. Flatten the whole structure into a single sorted list that uses only the bottom pointers, and return its head. In the result every next pointer must be null.

We write k for the number of vertical lists (columns) and N for the total number of nodes. The heads of the columns are not required to be sorted relative to each other; none of the methods below rely on it.

static class Node {
    int data;
    Node next, bottom;
    Node(int data) { this.data = data; }
}

Example 1

5 -> 10 -> 19 -> 28        (next pointers along the top)
|    |     |     |
7    20    22    35        (bottom pointers going down)
|          |     |
8          50    40
|                |
30               45

answer: 5 7 8 10 19 20 22 28 30 35 40 45 50   (linked by bottom)

Example 2

columns [10, 20], [20, 30], [5]
answer: 5 10 20 20 30     // duplicates stay; the column heads were not sorted

Approach 1: Brute force, collect and sort

Intuition. Ignore the structure: the answer is just all the values in sorted order. Collect every node into an array, sort the array by value, and relink the nodes through bottom in that order. Relinking the existing nodes (rather than creating new ones) keeps the result made of the original nodes, which is what the problem expects.

Algorithm.

  1. Walk the columns with next, and each column with bottom, adding every node to a list.
  2. Sort the list by data.
  3. For each position i, set next = null and bottom to the node at i + 1 (or null for the last one).
  4. Return the first node, or null if there were none.
static Node bruteForce(Node root) {
    List<Node> all = new ArrayList<>();
    for (Node col = root; col != null; col = col.next) {
        for (Node cur = col; cur != null; cur = cur.bottom) all.add(cur);
    }
    all.sort((x, y) -> Integer.compare(x.data, y.data));
    for (int i = 0; i < all.size(); i++) {
        Node node = all.get(i);
        node.next = null;                           // the result uses bottom pointers only
        node.bottom = (i + 1 < all.size()) ? all.get(i + 1) : null;
    }
    return all.isEmpty() ? null : all.get(0);
}

Complexity. Time O(N log N) for the sort. Space O(N) for the list of nodes.

The approach throws away the most useful fact we were given: every column is already sorted. Merging sorted lists is cheaper than sorting from scratch.

Approach 2: Better, merge the columns one by one

Intuition. Merging two sorted linked lists into one sorted list is a classic linear-time routine: keep a tail pointer, repeatedly attach the smaller of the two front nodes, and append the leftovers at the end. Flattening k columns is just merging them all. A neat way to organise this is recursion from the right: flatten everything to the right of the first column (the recursive call returns one sorted bottom list), then merge the first column into that result.

Before merging, we clear the first column’s next pointer. Its job (pointing at the next column) is finished once the recursive call has used it, and the result must not keep any next links. All other nodes already have next == null, because only column heads ever had one.

Algorithm.

  1. If root is null or has no next, it is already a single sorted column; return it.
  2. rest = mergeFromRight(root.next).
  3. root.next = null.
  4. Return merge(root, rest).
static Node mergeFromRight(Node root) {
    if (root == null || root.next == null) return root;
    Node rest = mergeFromRight(root.next);          // already one sorted bottom list
    root.next = null;
    return merge(root, rest);
}

static 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;              // one side is exhausted, append the other
    return dummy.bottom;
}

Dry run on Example 1 (the recursion unwinds from the right):

merge left column right side (already flat) result
1 19 22 50 28 35 40 45 19 22 28 35 40 45 50
2 10 20 19 22 28 35 40 45 50 10 19 20 22 28 35 40 45 50
3 5 7 8 30 10 19 … 50 5 7 8 10 19 20 22 28 30 35 40 45 50

Complexity. Time O(N × k) in the worst case: the accumulated list grows with every merge, and each merge walks up to its full length. With k columns of about N / k nodes, the merges cost roughly 2N/k + 3N/k + ... + N, which is O(N × k). Space O(k) for the recursion stack; no new nodes except one dummy per merge.

Using <= in merge takes from the left list on ties, so equal values keep a stable order. Either choice produces a correctly sorted list.

This is the solution most interviewers expect for this problem, since the inputs are small and it uses no auxiliary data structure. When k is large, however, the repeated re-walking of the growing list hurts.

Approach 3: Optimal for many columns, a min-heap

Intuition. At any moment, the smallest node not yet placed must be at the front of some column, because each column is sorted. So we only ever need to compare the current fronts of the k columns. A min-heap gives the smallest of k items in O(log k). Poll the smallest node, append it to the result, and push its bottom successor (the new front of that column) into the heap. This is the standard k-way merge.

Algorithm.

  1. Push the head of every column into a min-heap ordered by data.
  2. While the heap is not empty: poll smallest; if it has a bottom, push it; clear smallest.next; append smallest after tail.
  3. Return dummy.bottom.
static Node minHeap(Node root) {
    PriorityQueue<Node> heap = new PriorityQueue<>((x, y) -> Integer.compare(x.data, y.data));
    for (Node col = root; col != null; col = col.next) heap.add(col);
    Node dummy = new Node(0), tail = dummy;
    while (!heap.isEmpty()) {
        Node smallest = heap.poll();
        if (smallest.bottom != null) heap.add(smallest.bottom);   // its successor joins the race
        smallest.next = null;
        tail.bottom = smallest;
        tail = smallest;
    }
    return dummy.bottom;                            // the last node polled has bottom == null already
}

The successor smallest.bottom is read before smallest is attached anywhere, and attaching it only changes the previous tail’s bottom, so no link is lost. When the heap becomes empty, the last polled node had no bottom (otherwise it would have pushed it), so the result is already terminated by null.

Complexity. Time O(N log k): every node enters and leaves the heap once, and the heap never holds more than k nodes. Space O(k) for the heap.

The comparator uses Integer.compare rather than x.data - y.data; subtraction can overflow for values of opposite sign near the int limits and produce a wrong order.

Edge cases and pitfalls