deepSWE.io

Merge K Sorted Lists

HeapLinked List

20 min

Problem Statement

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

Example 1:

List 1

List 2

List 3

Merged List

Constraints

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

Solution (Min-Heap)

The most efficient way to solve this problem is by using a min-heap. We can insert the first node of each of the k lists into the min-heap. Then, we repeatedly extract the minimum node from the heap, add it to our result list, and insert the next node from the same list into the heap.

Algorithm Steps

Create a min-heap and insert the first node of each linked list.
While the heap is not empty, extract the node with the smallest value.
Add the extracted node to the result list.
If the extracted node has a next node, insert it into the heap.
Repeat until the heap is empty.

Initial Lists

Min-Heap

Result List

Start: Initialize a min-heap with the first element of each list.

Merge K Sorted Lists Solution


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]:
        heap = []
        for i, l in enumerate(lists):
            if l:
                heapq.heappush(heap, (l.val, i, l))
        
        head = ListNode()
        curr = head
        
        while heap:
            val, i, node = heapq.heappop(heap)
            curr.next = node
            curr = curr.next
            if node.next:
                heapq.heappush(heap, (node.next.val, i, node.next))
                
        return head.next