{x}
blog image

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 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.

Solution Explanation: Merging k Sorted Linked Lists

This problem involves merging k sorted linked lists into a single sorted linked list. Several approaches can solve this, but the most efficient uses a priority queue (min-heap). Let's break down the min-heap approach and its implementation in various programming languages.

Approach: Min-Heap

A min-heap data structure is ideal because it efficiently keeps track of the smallest element across all lists. The algorithm works as follows:

  1. Initialization: Create a min-heap. Add the head node of each non-empty input linked list to the heap. The priority of each node in the heap is its value.

  2. Iteration: While the heap is not empty:

    • Extract the minimum element (node) from the heap. This will be the next smallest node overall.
    • Append this node to the result linked list.
    • If the extracted node has a next node, add that next node to the heap.

  3. Result: The result linked list, built by appending the minimum nodes, is the merged sorted linked list.

Time and Space Complexity

  • Time Complexity: The time complexity is dominated by the heap operations. In the worst case, we insert and extract n nodes (where n is the total number of nodes across all k lists). Insertion and extraction from a heap take O(log k) time, where k is the number of linked lists (the size of the heap). Therefore, the overall time complexity is O(n log k).

  • Space Complexity: The space complexity is O(k) because the heap holds at most one node from each of the k lists.

Code Implementation

The code implementations below demonstrate the min-heap approach in several programming languages. Note that the specific implementation details of the min-heap (priority queue) may vary slightly between languages. Some languages have built-in priority queue structures, while others may require using a library or implementing it from scratch.

Python

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[ListNode | None]) -> ListNode | None:
        heap = []
        for i, head in enumerate(lists):
            if head:
                heapq.heappush(heap, (head.val, i, head))  # (value, list_index, node)
 
        dummy = ListNode()
        tail = dummy
        while heap:
            _, i, node = heapq.heappop(heap)
            tail.next = node
            tail = tail.next
            if node.next:
                heapq.heappush(heap, (node.next.val, i, node.next))
 
        return dummy.next

Java

import java.util.PriorityQueue;
 
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
 
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>( (a, b) -> a.val - b.val);
        for (ListNode node : lists) {
            if (node != null) pq.offer(node);
        }
 
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while (!pq.isEmpty()) {
            ListNode curr = pq.poll();
            tail.next = curr;
            tail = tail.next;
            if (curr.next != null) pq.offer(curr.next);
        }
        return dummy.next;
    }
}

C++

#include <queue>
 
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
 
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq;
        for (auto list : lists) {
            if (list) pq.push(list);
        }
 
        ListNode* dummy = new ListNode();
        ListNode* tail = dummy;
        while (!pq.empty()) {
            ListNode* curr = pq.top();
            pq.pop();
            tail->next = curr;
            tail = tail->next;
            if (curr->next) pq.push(curr->next);
        }
        return dummy->next;
    }
};

//Other languages implementations can be added similarly, adapting the priority queue implementation to the language's specifics. The core logic remains the same.