HardLinked ListDivide and ConquerHeap (Priority Queue)Merge Sort

Merge k Sorted Lists

1 approach, code in every language

You are given an array of k linked lists, where each individual list is already sorted in ascending order by node value.

Merge every list into a single sorted linked list and return the head of that combined list. The result must preserve ascending order across all nodes drawn from every input list.

Some of the input lists may be empty, and the whole array itself may be empty, in which case the merged result is an empty list.

Example 1

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

Output: [1,1,2,3,4,4,5,6]

The three sorted lists are 1->4->5, 1->3->4 and 2->6. Interleaving them in ascending order produces 1->1->2->3->4->4->5->6.

Example 2

Input: lists = []

Output: []

There are no lists to merge, so the result is the empty list.

Constraints

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
Each lists[i] is sorted in ascending order
The sum of lists[i].length will not exceed 10^4

Min-Heap of List Heads

Keep one candidate per list in a min-heap and repeatedly pop the global minimum.

Loading animation…

Intuition

Because each of the k input lists is already sorted, the smallest unused element across all lists is always sitting at one of the current list heads. A min-heap lets us fetch that global minimum in O(log k) time instead of rescanning all k heads every step. We seed the heap with every non-empty head, then repeatedly pop the smallest node, append it to the output, and push its successor if one exists. This keeps the heap size bounded by k while we drain all N nodes. An alternative is divide-and-conquer: pair up the lists and merge them two at a time, halving the count of lists each round, which reaches the same O(N log k) time without an explicit heap.

Algorithm walkthrough

1Create a dummy head with a tail pointer, and push the head node of every non-empty list into a min-heap ordered by node value.
2Pop the node holding the smallest value from the heap.
3Append that node to the tail of the output list and advance the tail pointer.
4If the popped node has a next node, push that successor into the heap.
5Repeat until the heap is empty.
6Return dummy.next, which is the head of the fully merged list.

Implementation

import heapq

class Solution:
    def mergeKLists(self, lists: list[ListNode]) -> ListNode:
        heap = []
        # Use the list index as a tie-breaker so nodes are never compared directly.
        for i, node in enumerate(lists):
            if node:
                heapq.heappush(heap, (node.val, i, node))

        dummy = ListNode(0)
        tail = dummy
        while heap:
            _, i, node = heapq.heappop(heap)
            tail.next = node
            tail = node
            if node.next:
                heapq.heappush(heap, (node.next.val, i, node.next))
        return dummy.next

Time

O(N log k)

Space

O(k)

N is the total number of nodes and k is the number of lists. The heap holds at most k nodes, and each of the N nodes is pushed and popped once at O(log k) per operation.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Merge Shard Streams is our own problem on the technique behind Merge k Sorted Lists: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free