Start learning free

LESSON 282 OF 344 · LINKED LISTS

Merge K Sorted Lists in Java: O(n log k) with a PriorityQueue

Practice O(N log k) Read the full explanation

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

 

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

 

Constraints:

  • k == lists.length
  • 0 <= k <= 104
  • 0 <= lists[i].length <= 500
  • -104 <= lists[i][j] <= 104
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length will not exceed 104.
Note:

Your algorithm should run in O(n log k) time and use O(k) extra space, where n is the total number of nodes across all lists and k is the number of lists.


Hints:

The brute force re-scans every list head each time. What data structure gives you the smallest of k values in O(log k) instead of O(k)?

Use a min-heap seeded with the head of every non-empty list, ordered by node.val.
Each iteration: extract the smallest node, append a copy of its value to the merged tail, and if it has a successor, push that successor onto the heap.
When the heap is empty, every list has been fully consumed.

The heap holds at most k nodes at any time. Each of the n output nodes costs one extract and at most one insert, each O(log k) — Time Complexity is O(n log k).
The heap itself uses O(k) extra space.

STEP 1 OF 11
    Ctrl + Enter to check

    JAVA · LINKED LISTS

    Merge K Sorted Lists in Java, explained

    Problem overview

    The method mergeKLists receives an array lists of k singly linked lists, each sorted in ascending order, and returns one sorted linked list holding all their values. Entries in the array can be null, which stands for an empty list, and the array itself can be empty.

    For lists = [[1,4,5],[1,3,4],[2,6]] the result is 1->1->2->3->4->4->5->6. For an empty array, or for an array whose only entry is an empty list, the result is an empty list, which means null.

    The statement asks for O(n log k) time and O(k) extra space, where n is the total number of nodes and k the number of lists.

    Approach: a min-heap of list fronts

    At any moment, the next value in the merged list is the smallest among the current front nodes of the k lists. The simple method scans all k fronts for every output node, which costs O(k) per node and O(n * k) overall.

    A min-heap does better. It is a structure that always gives you its smallest element quickly: taking the smallest or adding an element costs O(log k) for a heap of k elements. The plan:

    1. Put the head of every non-empty list into the heap, ordered by the node's value.
    2. Repeatedly take the smallest node out and append its value to the result.
    3. If the node that was taken has a successor, put the successor into the heap. This node is the new front of that list.
    4. Stop when the heap is empty. Every list has then been consumed.

    The heap never holds more than one node per list, so its size is at most k. Each of the n output nodes costs one removal and at most one insertion, each O(log k), which gives O(n log k).

    On the example, the heap starts with the nodes 1 (from the first list), 1 (second list) and 2. The first removal gives a 1, and its successor 4 enters the heap. The heap now holds 4, 1 and 2, so the next removal gives the other 1, and its successor 3 enters. The process continues until it has produced 1, 1, 2, 3, 4, 4, 5, 6.

    Step by step

    1. Create the heap. A PriorityQueue<ListNode> called minNodes. It can't order ListNode objects by itself, so you give it a comparator that compares the val field.
    2. Visit every list head with an enhanced for loop over lists.
    3. Add only non-null heads. A null head means an empty list, and the heap can't hold null.
    4. Create a sentinel node dummy. The merged list will start at dummy.next, which spares you a special case for the first node.
    5. Create the walker tail, set to dummy. It always points at the last node appended.
    6. Loop while the heap is not empty.
    7. Take the smallest node with poll() and keep it in minNode.
    8. Append a new node with the same value as tail.next. The merged list is built from fresh nodes, so the input lists are left unchanged.
    9. Feed the heap. If minNode.next is not null, add it. Each list refills the heap one node at a time.
    10. Move the walker with tail = tail.next.
    11. Return dummy.next, the head of the merged list. If nothing was ever added, it is null, the correct empty result.

    The solution in Java

    class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> minNodes = new PriorityQueue<>(Comparator.comparingInt(node -> node.val));
        for (ListNode head : lists) {
            if (head != null) {
                minNodes.add(head);
            }
        }
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while (!minNodes.isEmpty()) {
            ListNode minNode = minNodes.poll();
            tail.next = new ListNode(minNode.val);
            if (minNode.next != null) {
                minNodes.add(minNode.next);
            }
            tail = tail.next;
        }
        return dummy.next;
    }
}

    The Java details worth a closer look:

    • PriorityQueue is a min-heap by default. poll() removes and returns the smallest element according to the ordering, and returns null if the queue is empty. The loop condition makes sure it is never empty at that point. It is the add and poll calls that cost O(log k). Looking at the head with peek() is O(1).
    • The comparator. Comparator.comparingInt(node -> node.val) builds a comparator from a function that extracts an int key. Java infers the type of node as ListNode from the queue's declared type. Writing (a, b) -> a.val - b.val also works for values in the range of this lesson, but subtracting can overflow for large values of opposite sign, so comparingInt is the safer habit.
    • Without a comparator. A PriorityQueue of objects that are not Comparable throws a ClassCastException when you add a second element, so the comparator is required.
    • Equal values are fine. Two nodes with the same val are both stored in the heap. The order in which a PriorityQueue returns equal elements is not specified, but equal values give the same output either way.
    • The sentinel pattern. new ListNode() uses the no-argument constructor, so dummy.val is 0 and never read. Because tail and dummy refer to the same node at first, tail.next = ... also sets dummy.next.

    Complexity

    Let n be the total number of nodes and k the number of lists.

    Time: O(n log k). Seeding the heap with up to k heads costs O(k log k). Then the loop runs n times. Each run does one poll and at most one add on a heap of at most k nodes, so each costs O(log k). Since every non-empty list contributes at least one node, k is at most n among non-empty lists, and the total stays O(n log k).

    Space: O(k) extra. The heap holds at most one node per list. The merged list is the output and is not counted as extra space, though it does occupy O(n) memory.

    Edge cases and common mistakes

    • An empty array. The heap stays empty, the loop doesn't run, and dummy.next is null.
    • Null entries. [null] and [null, 1->2, null] work: null heads are skipped, so the heap never sees them.
    • Adding a null head. PriorityQueue.add(null) throws a NullPointerException, which is why the check comes first.
    • Forgetting to push the successor. The result would hold only the first node of each list.
    • Adding the whole list again. Push minNode.next, the next node, not minNode, which would loop forever.
    • Returning dummy. The sentinel is not part of the answer. Return dummy.next.
    • Duplicates. [[1], [1]] gives 1->1. Nothing is dropped.

    Testing

    • [[1,4,5],[1,3,4],[2,6]] gives [1,1,2,3,4,4,5,6].
    • [] gives [].
    • [[]] gives [].
    • [[], [-2, 7], []] gives [-2, 7].
    • [[5], [1]] gives [1, 5].
    Keep going with JavaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free