Flattening a Linked List

Hard20–25 min

Topics

Linked ListMerge Sort

Companies

AmazonMicrosoftFlipkart

Picture a collection of lists, each one already sorted, gathered together in some fixed order. Flatten every one of them into a single list that's still fully sorted, with every value from every original list included exactly once. This is the same shape as merging k sorted lists — it just arrives framed as separate sorted sub-lists that need combining rather than nodes with an extra pointer. Splitting the collection in half, recursively flattening each half down to one sorted list, and then merging those two results with a standard two-pointer splice keeps the total work proportional to N log k instead of degrading toward N times k if the lists were folded in one at a time.

Test Case 1:

Input:lists = [[5, 10], [2, 7], [1, 9]]

Output:[1, 2, 5, 7, 9, 10]

Explanation:Every value from all 3 already-sorted lists, merged into one fully sorted list.

Test Case 2:

Input:lists = [[3, 6, 9]]

Output:[3, 6, 9]

Explanation:A single list has nothing else to merge with.

Test Case 3:

Input:lists = [[], []]

Output:[]

Explanation:Every list is empty — nothing to flatten.

Constraints

◆1 ≤ number of top-level lists (k) ≤ 50
◆0 ≤ nodes per list ≤ 20
◆-1000 ≤ node value ≤ 1000
◆Each individual list is already sorted in increasing order

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Collect Every Value, Sort, Rebuild

Good

Walk every list in turn, copying every value into one array. Sort that array from scratch, then build a brand-new list from it. Correct, but it throws away the fact that each list was already individually sorted — it re-sorts everything as if the values had arrived in no particular order at all.

TimeO(N log N), where N is the total number of nodes across every list

SpaceO(N)

Java

Try it out

// Node definition used in this problem:
// class Node {
//     int val;
//     Node next;
// }

class Solution {
    public Node flatten(List<Node> lists) {
        List<Integer> vals = new ArrayList<>();
        for (Node head : lists) {
            Node curr = head;
            while (curr != null) {
                vals.add(curr.val);
                curr = curr.next;
            }
        }
        Collections.sort(vals);
        Node dummy = new Node(0);
        Node tail = dummy;
        for (int v : vals) {
            tail.next = new Node(v);
            tail = tail.next;
        }
        return dummy.next;
    }
}

Optimal — Divide and Conquer, Pairwise Merge

Optimal

Merging two already-sorted lists is a solved problem — the trick is reducing many lists down to that. Split the array of lists in half, recursively flatten each half down to a single sorted list, then merge those two results together with a standard two-pointer splice. Halving the problem at every level keeps the total work O(N log k), instead of the O(N·k) that merging the lists one at a time into a growing result would cost.

TimeO(N log k), where N is the total number of nodes and k is the number of lists

SpaceO(log k) recursion stack