Start learning free

LESSON 280 OF 338 · LINKED LISTS

Merge K Sorted Lists in Go: O(n log k) with a Min-Heap

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

    GO · LINKED LISTS

    Merge K Sorted Lists in Go, explained

    Problem overview

    The function mergeKLists receives a slice lists of k linked lists, each sorted in ascending order, and returns one sorted list holding all their values. For [[1,4,5],[1,3,4],[2,6]] the result is [1,1,2,3,4,4,5,6]. An empty slice gives an empty list, and so does a slice holding one empty list. Some entries of lists can be nil.

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

    Approach: always take the smallest front node

    Merging two sorted lists is a matter of comparing their front nodes and taking the smaller. For k lists the idea is the same: the next node of the merged list is the smallest of the k front nodes. Scanning all fronts for every output node costs O(k) each time, so O(n * k) in total.

    A min-heap does better. It is a structure that keeps its smallest element on top, with insertion and removal of the top both in O(log k). The heap holds at most one node from each list, the current front. The loop is:

    1. Seed the heap with the head of every non-empty list.
    2. Remove the smallest node and append its value to the output.
    3. If that node has a successor, push the successor, which is the new front of its list.
    4. Repeat until the heap is empty.

    Every list stays represented while it has nodes, and the heap never exceeds k entries. Each of the n nodes is pushed once and popped once, at O(log k) each, which gives O(n log k).

    On [[1,4,5],[1,3,4],[2,6]] the heap starts with the fronts 1, 1 and 2. Popping a 1 pushes that list's next node, 4 or 3. The heap then holds 1, 2 and a 4 or 3, and the loop continues in that way until all eight values have been output.

    Step by step

    1. Create the heap: minNodes := &minHeap{}. The lesson provides the minHeap type, which orders *ListNode entries by Val.
    2. Loop over the heads: for _, head := range lists. The blank identifier discards the index.
    3. Push non-nil heads with heap.Push(minNodes, head). An empty list has nothing to merge, and a nil node on the heap would crash the comparison.
    4. Create the dummy: dummy := &ListNode{}. The merged list will be dummy.Next.
    5. Keep a walker, tail := dummy, which always points at the last appended node.
    6. Loop while the heap is non-empty: for minNodes.Len() > 0. Go uses a for with only a condition for what other languages call while.
    7. Pop the smallest: minNode := heap.Pop(minNodes).(*ListNode). heap.Pop returns an any, so the type assertion recovers the *ListNode.
    8. Append a new node holding the value, as tail.Next. The code builds a fresh node instead of reusing minNode, so the input lists are not modified.
    9. Push the successor if minNode.Next != nil, so each list keeps feeding the heap one node at a time.
    10. Advance the walker: tail = tail.Next.
    11. Return dummy.Next, the head of the merged list.

    The solution in Go

    func mergeKLists(lists []*ListNode) *ListNode {
    minNodes := &minHeap{}
    for _, head := range lists {
        if head != nil {
            heap.Push(minNodes, head)
        }
    }
    dummy := &ListNode{}
    tail := dummy
    for minNodes.Len() > 0 {
        minNode := heap.Pop(minNodes).(*ListNode)
        tail.Next = &ListNode{Val: minNode.Val}
        if minNode.Next != nil {
            heap.Push(minNodes, minNode.Next)
        }
        tail = tail.Next
    }
    return dummy.Next
}

    The minHeap type is not part of the function. In Go, the container/heap package works with any type that implements heap.Interface: Len, Less, Swap, Push and Pop. A type like the following works with this solution:

    type minHeap []*ListNode

func (h minHeap) Len() int           { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h minHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x any)        { *h = append(*h, x.(*ListNode)) }
func (h *minHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

    Go details worth knowing:

    • Use the package functions, not the methods. The solution calls heap.Push(minNodes, head) and heap.Pop(minNodes), which restore the heap order after changing the slice. Calling the type's own Push and Pop methods directly only appends or removes the last slice element and breaks the ordering.
    • Pointer receivers. Push and Pop change the slice's length, so they need a pointer receiver, and the heap is passed around as *minHeap. That is why the solution creates it with &minHeap{}.
    • Type assertion. heap.Pop(...).(*ListNode) panics if the value has another dynamic type. The heap only ever holds *ListNode values, so it's safe.
    • The blank identifier. for _, head := range lists discards the index, since an unused variable would be a compile error.

    Complexity

    Time: O(n log k). Each of the n nodes is pushed at most once and popped once, and both operations cost O(log h) where h is the heap size, never more than k. Seeding the heap adds at most k pushes.

    Space: O(k) extra. The heap holds at most one node per list. The merged list has n new nodes, but that is the output and is not counted as extra space.

    Edge cases and common mistakes

    • No lists. With lists empty or nil, nothing is pushed, the loop doesn't run, and the function returns dummy.Next, which is nil.
    • Empty lists inside the slice. [nil] gives nil. The head != nil check keeps nil out of the heap, where Less would panic reading .Val.
    • Duplicates. Equal values from different lists are all kept: [1,4,5] and [1,3,4] give two 1s and two 4s.
    • Pushing the whole list. Only the front node of each list belongs on the heap. Pushing every node works, but costs O(n) space instead of O(k).
    • Forgetting the successor. If minNode.Next is never pushed, only the first node of each list reaches the output.
    • Calling the methods directly. minNodes.Push(head) instead of heap.Push(minNodes, head) compiles but leaves the slice unordered, so the output is not sorted.

    Testing

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