Leetcode - 23. Merge k Sorted Lists

Hard

Feb 18, 2026

#linked-list

#heap

23. Merge k Sorted Lists

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 linked list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

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.

Constraints:

Notes

Intuition

We want to take the smallest value at a time from each list and only iterate further on that list after a value is taken from that list.

Implementation

We can use a min-heap alongside keeping track of the pointers in array and accessing them via index. To start, we create our array of pointers to the lists. At the same time, we add the first element of each non-empty list to the heap along with its index (with the value as the priority).

After this, we iterate while the heap is not empty, we pop from the heap and add the new node to our resultant list. Using the index, we increment that specific pointer. Then, we check if the the updated pointer is not null (i.e. next is defined) and we push that value and its index to the heap. This will also ensure that whichever index is popped from the heap will be defined at that point.

Finally, return the result.

Edge-cases

Ensure to push the first elements from the non-empty lists from the heap to start so that we have something to iterate over.

Time: O(N log k): where N is the total number of nodes in all k lists. The main iteration is the heap iteration which will run once for each node in the result, on each iteration, we pop and potentially push to the heap which is O(log k) because the size of the heap will never exceed the starting size will be at most k.
Space: O(k): The only extra space is the heap which will have, at most, k elements

Complexity

Solution

from typing import List, Optional
from lcutils import ListNode
import heapq

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        k = len(lists)
        ptrs: List[Optional[ListNode]] = [None] * k
        heap = []
        for i in range(k):
            ptr = lists[i]
            ptrs[i] = ptr
            if ptr:
                heapq.heappush(heap, (ptr.val, i))
        
        dummy = ListNode(0)
        curr = dummy
        while heap:
            val, i = heapq.heappop(heap)
            curr.next = ListNode(val)
            curr = curr.next
            # will be defined because it was added
            ptrs[i] = ptrs[i].next
            if ptrs[i]:
                heapq.heappush(heap, (ptrs[i].val, i))
        return dummy.next



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()