Start learning free

LESSON 322 OF 442 · LINKED LISTS

Merge K Sorted Lists in Go: O(n * k) by Scanning the Heads

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 11
    Ctrl + Enter to check

    GO · LINKED LISTS

    Merge K Sorted Lists in Go, explained

    Problem overview

    mergeKLists(lists []*ListNode) receives a slice of k linked lists, each sorted in ascending order, and returns one sorted linked list holding all their values. A list node is a struct with a Val field and a Next pointer, and a list is represented by its first node, with nil standing for an empty list. The slice itself can be empty, and some or all of its lists can be empty.

    For lists = [[1,4,5],[1,3,4],[2,6]] the merged list is 1->1->2->3->4->4->5->6. For lists = [] and for lists = [[]] the answer is the empty list, nil.

    Approach: always take the smallest head

    Each input list is already sorted, so its smallest unused value is always at its front. The smallest unused value overall is therefore the smallest of the k front values. Take that one, put it at the end of the answer, and move that list forward by one node. Repeat until every list is used up.

    Finding the smallest front value is the simplest possible step: look at all k heads and keep the best. That scan costs O(k), and it happens once for each of the n values in the output, so the total is O(n * k), where n is the number of nodes across all lists. It is a brute-force method. A min-heap finds the smallest head in O(log k) instead, which brings the total down to O(n log k), and that has its own lesson.

    To build the answer, the solution uses a dummy node placed before the real head, plus a tail pointer that always refers to the last node appended. Because tail starts on the dummy, appending the first value is no different from appending any other, and the finished list starts at dummy.Next.

    Step by step

    1. Create the dummy node with dummy := &ListNode{}. Its value is never used.
    2. Create the walker tail := dummy. It always points at the last node of the merged list.
    3. Start an infinite loop with for { ... }. Go has no while keyword, and a bare for is the usual way to write a loop that ends with break.
    4. Declare ind := -1 at the top of each pass. It will hold the position of the list with the smallest head, and -1 means that none has been chosen yet.
    5. Scan all the lists with for i := 0; i < len(lists); i++.
    6. Update the best choice. If lists[i] is not nil and either nothing is chosen yet or its head value is strictly smaller than the chosen one's, set ind = i.
    7. Stop when the scan finds nothing. If ind is still -1, every list is empty, so break.
    8. Append a new node with the smallest value: tail.Next = &ListNode{Val: lists[ind].Val}.
    9. Advance the chosen list with lists[ind] = lists[ind].Next.
    10. Move tail onto the node just appended.
    11. Return dummy.Next, the head of the merged list.

    The solution in Go

    func mergeKLists(lists []*ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy
    for {
        ind := -1
        for i := 0; i < len(lists); i++ {
            if lists[i] != nil && (ind == -1 || lists[i].Val < lists[ind].Val) {
                ind = i
            }
        }
        if ind == -1 {
            break
        }
        tail.Next = &ListNode{Val: lists[ind].Val}
        lists[ind] = lists[ind].Next
        tail = tail.Next
    }
    return dummy.Next
}

    The Go details worth a closer look:

    • Pointers and nil. *ListNode is a pointer to a node, and nil means no node. The condition lists[i] != nil && ... relies on short-circuit evaluation: when the first part is false, lists[i].Val is never evaluated, so no nil pointer is dereferenced. Reading a field through a nil pointer would panic.
    • &ListNode{...} allocates. The composite literal with & creates a new node and gives back a pointer to it. Go decides where to store it and cleans it up automatically. There is no delete and no manual memory handling.
    • Fields left out are zero. &ListNode{} has Val 0 and Next nil. The new nodes get a Next of nil until the next pass links them.
    • The input nodes are copied, not relinked. The code creates a new node for each value and never changes an existing node's Next, so the original lists stay intact. The entries of the lists slice, however, are overwritten as they advance. When the function returns, every entry is nil. A caller that needs the slice afterwards should pass a copy.
    • Ties. The comparison is strictly <, so with equal heads the list with the smaller position wins. The merged values are the same either way.

    Complexity

    Time: O(n * k). The outer loop makes n + 1 passes: one for each output node and a last one that finds nothing and breaks. Every pass scans k heads. The other work in a pass is a constant amount.

    Space: O(1) beyond the answer. The merged list is built from one new node per value, as the output requires. Apart from that, the function keeps the dummy node and a few variables. Advancing lists[ind] reuses the input slice and allocates nothing.

    Edge cases and common mistakes

    • Empty slice. The scan loop doesn't run, ind stays -1, the function breaks at once and returns dummy.Next, which is nil.
    • Only empty lists. [nil] gives nil in the same way.
    • Some empty lists among others. They are skipped by the != nil test and never chosen.
    • Returning dummy. That would put a fake leading node in front of the answer. Return dummy.Next.
    • Dereferencing before the nil test. Writing the comparison as lists[i].Val < lists[ind].Val before checking lists[i] != nil panics on an exhausted list. Likewise lists[ind] is only read when ind is not -1, which the order of the conditions guarantees.
    • Forgetting to move tail. Each new node would be attached to the same place, overwriting the previous one, and the merged list would hold a single value.

    Testing

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