Start learning free

LESSON 318 OF 438 · LINKED LISTS

Merge K Sorted Lists in Java: O(n × k) with a Dummy Node

Practice O(n × 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] <= 107
  • 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 × k) time and use O(1) extra space apart from the merged list's new nodes (one per value), where n is the total number of nodes across all lists and k is the number of lists.
(A faster O(n log k) solution, with a min-heap, has its own lesson.)


Hints:

The output is sorted: at every moment you only need the smallest current head across all lists.
What's the simplest way to find it?

Use a dummy sentinel node and a tail walker.
Each iteration: scan all k heads, pick the smallest, append a new node with its value after tail, move tail onto it, and advance the chosen list. Repeat until every list is exhausted.

We produce n output nodes, and each one costs an O(k) scan of all heads — Time Complexity is O(n × k).
Apart from the merged list it returns (one new node per value), the solution keeps only the dummy node and a few variables, so the Extra Space is O(1).
STEP 1 OF 14
    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. It must return one sorted linked list that holds every value from all of them. Some lists can be empty (null), and the array itself can be empty.

    In the first example, the lists are 1->4->5, 1->3->4 and 2->6. Merged, they give 1->1->2->3->4->4->5->6. An empty array and an array holding a single empty list both give an empty list, which in Java is null.

    The lesson asks for O(n × k) time, where n is the total number of nodes and k is the number of lists, and O(1) extra space apart from the list you return.

    Approach: always take the smallest head

    Every input list is already sorted, so the smallest value that hasn't been used yet is always at the front of one of the lists. Compare the current heads of all the lists, take the smallest, and repeat. After n rounds every value has been taken, in sorted order.

    Finding the smallest head means looking at all k heads, which costs O(k). Doing that once for each of the n output nodes gives O(n × k). This is the plain, brute-force version of the idea. A min-heap makes each round O(log k) and has its own lesson. Another option is to merge the lists two at a time, which is also faster. Here the point is to get the pointer work right with the simplest possible search.

    The output list is built with a dummy node: a throwaway node placed before the real head. Without it, appending the first node would be a special case, because there is no previous node to attach it to. With it, every append is the same statement, and the answer is dummy.next at the end.

    Step by step

    1. Create the dummy node. The merged list will hang off dummy.next.
    2. Keep a tail pointer to the last node appended. It starts on the dummy.
    3. Loop while any list still has nodes. A helper, anyNonNull, answers that, and the method defines it at the end.
    4. Start each round with ind = -1. This variable holds the index of the list with the smallest head, and -1 means no candidate yet.
    5. Scan all k lists with a counted loop. This scan is the O(k) cost paid per output node.
    6. Update the candidate. A list competes only if it isn't null. It wins if no candidate exists yet or its head value is strictly smaller than the candidate's.
    7. Append a new node with the winning value after tail.
    8. Advance the winning list by one node, so its next value becomes its head.
    9. Move tail onto the node you just appended.
    10. Return dummy.next once the loop ends.
    11. Write the helper. It is a private method that takes the array, and a for-each loop returns true at the first list that isn't null.
    12. Return false after that loop. Every entry was null, so the merge is done.

    The solution in Java

    class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while (anyNonNull(lists)) {
            int ind = -1;
            for (int i = 0; i < lists.length; i++) {
                if (lists[i] != null && (ind == -1 || lists[i].val < lists[ind].val)) {
                    ind = i;
                }
            }
            tail.next = new ListNode(lists[ind].val);
            lists[ind] = lists[ind].next;
            tail = tail.next;
        }
        return dummy.next;
    }

    private boolean anyNonNull(ListNode[] lists) {
        for (ListNode l : lists) {
            if (l != null) {
                return true;
            }
        }
        return false;
    }
}

    Java details worth a closer look:

    • Short-circuit && and ||. The condition checks lists[i] != null first, so lists[i].val is only read when the list exists. Likewise ind == -1 comes before lists[ind].val, so the code never reads lists[-1], which would throw an ArrayIndexOutOfBoundsException.
    • The input array is changed. lists[ind] = lists[ind].next overwrites array entries. The nodes themselves are never modified, because the result is built from new ListNode objects, but the caller's array ends up full of nulls. Callers who need the original heads afterwards should keep their own copies of them.
    • dummy is built with the no-argument constructor, so its val is 0. That value is never read, since the dummy is never returned.
    • Strict < keeps equal values in list order. When two heads are equal, the earlier list keeps the candidate slot. For plain integers the output is the same either way.
    • An empty result is null. If no list has nodes, the loop never runs and dummy.next is null.

    Complexity

    Time: O(n × k). The outer loop runs once per output node, so n times. Each round runs anyNonNull, which stops at the first non-empty list and costs at most O(k), and then scans k heads. Both are O(k), so a round costs O(k) and the total is O(n × k).

    Space: O(1) extra. The merged list needs one new node per value, but that is the output. Besides it, the method keeps the dummy node, tail, ind and a loop counter.

    Edge cases and common mistakes

    • An empty array. lists = [] makes anyNonNull return false at once, and the method returns null.
    • Lists that are null. [null] also gives an empty result, and [null, 2->..., null] works because the scan skips null entries. Comparing lists[i].val without the null check throws a NullPointerException.
    • Forgetting to advance the list. If lists[ind] never moves forward, the same head is chosen forever and the loop never ends.
    • Not moving tail. Without tail = tail.next, every new node overwrites the previous one, and the result has a single node.
    • Returning dummy instead of dummy.next. That adds a stray leading node with value 0.
    • Duplicate values across lists. Both 1s in the example appear in the output. A merge keeps duplicates.

    Testing

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