LeetCode 23 - Merge k Sorted Lists

The problem gives us an array of k sorted linked lists. Each linked list is already sorted in ascending order, and our task is to combine all of them into one single sorted linked list. A linked list node contains a value and a pointer to the next node.

leetcodehardlinked-listdivide-and-conquerheap-(priority-queue)merge-sort

LeetCode Problem 23

Difficulty: 🔴 Hard
Topics: Linked List, Divide and Conquer, Heap (Priority Queue), Merge Sort

Solution

Problem Understanding

The problem gives us an array of k sorted linked lists. Each linked list is already sorted in ascending order, and our task is to combine all of them into one single sorted linked list.

A linked list node contains a value and a pointer to the next node. The input is therefore not a normal array merge problem, because we cannot directly index into the lists. Instead, we must traverse nodes sequentially.

For example, if we are given:

1 -> 4 -> 5
1 -> 3 -> 4
2 -> 6

the final merged linked list should be:

1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

The key observation is that every individual list is already sorted. We should take advantage of this property instead of collecting all values and sorting them again from scratch.

The constraints are important:

  • There can be up to 10^4 linked lists
  • The total number of nodes across all lists is at most 10^4
  • Each individual list is already sorted

These constraints tell us that the solution must scale efficiently with both the number of lists and the number of nodes. A naive repeated merge approach can become inefficient when k is large.

Several edge cases are important:

  • lists may be empty
  • Some lists may themselves be empty
  • All lists may be empty
  • There may be only one linked list
  • Values can be duplicated
  • Negative numbers are allowed

The problem guarantees that every individual list is sorted in ascending order, which is the property that enables efficient merging techniques.

Approaches

Brute Force Approach

The simplest idea is to collect every node value from all linked lists into an array, sort the array, and then rebuild a new linked list from the sorted values.

This approach works because sorting all node values globally guarantees the final order is correct.

The algorithm would look like this:

  1. Traverse every linked list
  2. Store every value in an array
  3. Sort the array
  4. Create a new linked list from the sorted values

Although correct, this solution ignores the fact that the lists are already sorted. Sorting all values again introduces unnecessary work.

If the total number of nodes is N, sorting requires O(N log N) time.

Optimal Approach

The better solution uses a min heap, also called a priority queue.

The key insight is that we only need to know the smallest current node among all lists at any moment.

Since each list is sorted:

  • The smallest remaining node from a list is always at its head
  • We can keep the current head of each list inside a min heap
  • The heap allows us to retrieve the globally smallest node efficiently

Every time we remove the smallest node from the heap:

  • We append it to the result
  • We insert that node's next element into the heap

This guarantees that the heap always contains the smallest available candidates.

This approach avoids re-sorting everything and efficiently merges all lists in O(N log k) time, where:

  • N is the total number of nodes
  • k is the number of linked lists

Because k is often much smaller than N, this is significantly more efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(N log N) O(N) Collect all values, sort them, rebuild list
Optimal O(N log k) O(k) Use a min heap to track smallest current nodes

Algorithm Walkthrough

Heap-Based Merge Algorithm

  1. Create an empty min heap.

The heap will store the current smallest available node from each linked list. Since heaps efficiently return the minimum element, they are ideal for repeatedly selecting the next smallest node. 2. Insert the head node of every non-empty linked list into the heap.

At this point, the heap contains at most k elements, one from each list. 3. Create a dummy head node for the result linked list.

Using a dummy node simplifies list construction because we avoid handling special cases for the first insertion. 4. Repeatedly extract the smallest node from the heap.

The heap guarantees that the extracted node is globally the smallest remaining node among all lists. 5. Append the extracted node to the result linked list.

Move the result pointer forward after attaching the node. 6. If the extracted node has a next node, insert that next node into the heap.

Since the original list is sorted, the next node becomes the next candidate from that list. 7. Continue until the heap becomes empty.

Once the heap is empty, all nodes have been processed and merged into the result. 8. Return dummy.next.

The dummy node itself is not part of the final answer.

Why it works

The algorithm maintains an important invariant:

  • The heap always contains the smallest unprocessed node from each list.

Because each individual list is sorted, once a node is removed from a list, the next node in that list is the next smallest candidate from that list.

The heap guarantees that we always choose the globally smallest available node, so the final merged list is correctly sorted.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

import heapq
from typing import List, Optional

class Solution:
    def mergeKLists(
        self,
        lists: List[Optional[ListNode]]
    ) -> Optional[ListNode]:

        min_heap = []

        for index, node in enumerate(lists):
            if node:
                heapq.heappush(min_heap, (node.val, index, node))

        dummy = ListNode(0)
        current = dummy

        while min_heap:
            _, index, node = heapq.heappop(min_heap)

            current.next = node
            current = current.next

            if node.next:
                heapq.heappush(
                    min_heap,
                    (node.next.val, index, node.next)
                )

        return dummy.next

The implementation begins by initializing a min heap. Python's heapq module implements a binary min heap efficiently.

Each heap entry contains:

(node.val, index, node)

The value is used for ordering. The index is included because Python cannot directly compare ListNode objects when two values are equal. The index acts as a tiebreaker.

Next, we iterate through all linked lists and insert every non-empty head node into the heap.

A dummy node is then created to simplify result list construction. The current pointer always points to the last node in the merged list.

Inside the main loop:

  • The smallest node is extracted from the heap
  • That node is appended to the result
  • If the node has a successor, the successor is pushed into the heap

This process continues until all nodes are consumed.

Finally, dummy.next is returned because the dummy node itself is only a placeholder.

Go Solution

package main

import "container/heap"

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

type HeapNode struct {
	node *ListNode
}

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 interface{}) {
	*h = append(*h, x.(*ListNode))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)

	node := old[n-1]
	*h = old[:n-1]

	return node
}

func mergeKLists(lists []*ListNode) *ListNode {
	minHeap := &MinHeap{}
	heap.Init(minHeap)

	for _, node := range lists {
		if node != nil {
			heap.Push(minHeap, node)
		}
	}

	dummy := &ListNode{}
	current := dummy

	for minHeap.Len() > 0 {
		node := heap.Pop(minHeap).(*ListNode)

		current.Next = node
		current = current.Next

		if node.Next != nil {
			heap.Push(minHeap, node.Next)
		}
	}

	return dummy.Next
}

The Go solution follows the same algorithmic logic as the Python version, but Go requires explicitly implementing the heap interface from the container/heap package.

The custom MinHeap type defines:

  • Len
  • Less
  • Swap
  • Push
  • Pop

Go uses nil instead of Python's None, so all empty list checks use nil.

Unlike Python, Go does not require a tie-breaking index because heap comparisons are handled entirely through the Less function.

Worked Examples

Example 1

Input:

lists = [[1,4,5],[1,3,4],[2,6]]

Initial heap contents:

Heap Values
1, 1, 2

Step-by-step execution

Step Extracted Node Result List Inserted Into Heap
1 1 1 4
2 1 1 -> 1 3
3 2 1 -> 1 -> 2 6
4 3 1 -> 1 -> 2 -> 3 4
5 4 1 -> 1 -> 2 -> 3 -> 4 5
6 4 1 -> 1 -> 2 -> 3 -> 4 -> 4 none
7 5 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 none
8 6 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 none

Final result:

1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

Example 2

Input:

lists = []

Since there are no linked lists:

  • The heap starts empty
  • The loop never runs
  • dummy.next is None

Output:

[]

Example 3

Input:

lists = [[]]

The single list is empty:

  • No nodes are inserted into the heap
  • The heap remains empty
  • The algorithm immediately returns None

Output:

[]

Complexity Analysis

Measure Complexity Explanation
Time O(N log k) Each of the N nodes is inserted and removed from the heap once
Space O(k) The heap stores at most one node from each list

The heap never contains more than k elements because we only keep one active candidate node from each linked list.

Each heap insertion and removal operation costs O(log k), and we perform these operations once for every node.

Therefore, the total runtime becomes:

O(N log k)

This is significantly better than globally sorting all values when k is much smaller than N.

Test Cases

# Helper utilities for testing

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    dummy = ListNode()
    current = dummy

    for value in values:
        current.next = ListNode(value)
        current = current.next

    return dummy.next

def to_array(head):
    result = []

    while head:
        result.append(head.val)
        head = head.next

    return result

solution = Solution()

# Example 1
lists = [
    build_list([1, 4, 5]),
    build_list([1, 3, 4]),
    build_list([2, 6])
]
assert to_array(solution.mergeKLists(lists)) == [1,1,2,3,4,4,5,6]  # standard merge case

# Example 2
lists = []
assert to_array(solution.mergeKLists(lists)) == []  # empty input array

# Example 3
lists = [None]
assert to_array(solution.mergeKLists(lists)) == []  # single empty list

# Single list
lists = [build_list([1, 2, 3])]
assert to_array(solution.mergeKLists(lists)) == [1,2,3]  # already sorted single list

# Multiple empty lists
lists = [None, None, None]
assert to_array(solution.mergeKLists(lists)) == []  # all lists empty

# Negative numbers
lists = [
    build_list([-10, -5, 0]),
    build_list([-6, -2, 3])
]
assert to_array(solution.mergeKLists(lists)) == [-10,-6,-5,-2,0,3]  # negative values

# Duplicate values
lists = [
    build_list([1, 1, 1]),
    build_list([1, 1])
]
assert to_array(solution.mergeKLists(lists)) == [1,1,1,1,1]  # duplicate handling

# Different sized lists
lists = [
    build_list([1]),
    build_list([2, 3, 4, 5]),
    build_list([0])
]
assert to_array(solution.mergeKLists(lists)) == [0,1,2,3,4,5]  # uneven lengths

# Large k with small lists
lists = [build_list([i]) for i in range(100)]
assert to_array(solution.mergeKLists(lists)) == list(range(100))  # many lists

# Interleaving values
lists = [
    build_list([1, 4, 7]),
    build_list([2, 5, 8]),
    build_list([3, 6, 9])
]
assert to_array(solution.mergeKLists(lists)) == [1,2,3,4,5,6,7,8,9]  # alternating merges
Test Why
Standard merge example Validates normal operation
Empty input array Ensures no crash on empty lists
Single empty list Verifies handling of None lists
Single sorted list Confirms already sorted input works
Multiple empty lists Ensures heap initialization handles empties
Negative numbers Validates ordering with negatives
Duplicate values Confirms duplicates are preserved
Different sized lists Tests uneven linked list lengths
Large number of lists Stresses heap behavior with large k
Interleaving values Validates repeated heap updates

Edge Cases

Empty input array

One important edge case is when lists = [].

A naive implementation might assume at least one linked list exists and immediately access lists[0], causing an index error.

This implementation safely handles the case because the heap initialization loop simply does nothing. The heap remains empty, the main loop never executes, and the algorithm correctly returns None.

Lists containing only empty linked lists

Another subtle case is:

lists = [[], [], []]

or equivalently:

[None, None, None]

Some implementations accidentally push None into the heap, which causes comparison failures later.

This solution explicitly checks:

if node:

before insertion, so only valid nodes enter the heap.

Duplicate values across lists

When multiple lists contain the same value, Python's heap implementation attempts to compare the next tuple element if the first values are equal.

Without a tie-breaker index, Python would attempt to compare ListNode objects directly, raising a TypeError.

This implementation avoids the issue by storing:

(node.val, index, node)

The integer index guarantees tuples remain comparable even when node values are identical.