23. Merge k Sorted Lists – Leetcode Solutions

June 8, 2024

Table of Contents

Description:

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.

Examples:

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: []

Solution in Python:

To solve the problem of merging k sorted linked lists into one sorted linked list, we can use a min-heap (priority queue) to efficiently merge the lists. Here’s a step-by-step solution with detailed comments:

Understanding the problem:
- We are given an array of k linked lists, each of which is sorted in ascending order.
- We need to merge these linked lists into a single sorted linked list.
Approach:
- Use a min-heap to keep track of the smallest elements of each list.
- Initialize the heap with the head of each linked list.
- Continuously extract the smallest element from the heap, add it to the merged list, and then insert the next element from the same list into the heap.
- Repeat the above step until the heap is empty.
Implementation:
- Define the ListNode class if it is not already defined.
- Define the mergeKLists function.
- Use the heapq library in Python to manage the heap operations.

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):
        # Create a min-heap
        min_heap = []
        
        # Push the head node of each list into the min-heap
        for i, l in enumerate(lists):
            if l:
                heapq.heappush(min_heap, (l.val, i, l))
        
        # Create a dummy head for the result linked list
        dummy = ListNode()
        current = dummy
        
        # While there are elements in the heap
        while min_heap:
            # Pop the smallest element from the heap
            val, i, node = heapq.heappop(min_heap)
            current.next = ListNode(val)
            current = current.next
            # If there is a next node in the same list, push it into the heap
            if node.next:
                heapq.heappush(min_heap, (node.next.val, i, node.next))
        
        # Return the merged linked list
        return dummy.next

Detailed Comments:

Heap Initialization:
- We create an empty min-heap (min_heap = []).
- For each linked list in lists, if the list is not empty (if l:), we push the tuple (node value, list index, node) into the heap. This ensures that we keep track of the value, the index of the list it came from, and the node itself.
Merging Process:
- We initialize a dummy head (dummy = ListNode()) and a pointer current to track the end of the merged list.
- While the heap is not empty:
  - Extract the smallest element from the heap (val, i, node = heapq.heappop(min_heap)).
  - Append this node to the merged list (current.next = ListNode(val) and update the pointer current = current.next).
  - If the extracted node has a next node (if node.next:), push the next node into the heap (heapq.heappush(min_heap, (node.next.val, i, node.next))).
Return Result:
- Finally, return the merged list starting from dummy.next.

This approach ensures that we always extract the smallest element available, maintaining the order in the final merged list. The use of a heap allows us to efficiently manage the merging process, resulting in a time complexity of O(N log k), where N is the total number of nodes in all lists and k is the number of linked lists.

Solution in Javascript:

JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */

class MinHeap {
    constructor() {
        this.heap = [];
    }

    // Helper method to get the parent index
    parentIndex(index) {
        return Math.floor((index - 1) / 2);
    }

    // Helper method to get the left child index
    leftChildIndex(index) {
        return 2 * index + 1;
    }

    // Helper method to get the right child index
    rightChildIndex(index) {
        return 2 * index + 2;
    }

    // Method to insert a value into the heap
    insert(val) {
        this.heap.push(val);
        this.heapifyUp();
    }

    // Method to heapify up the inserted value
    heapifyUp() {
        let index = this.heap.length - 1;
        while (index > 0) {
            const parent = this.parentIndex(index);
            if (this.heap[parent][0] <= this.heap[index][0]) break;
            [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]];
            index = parent;
        }
    }

    // Method to extract the minimum value from the heap
    extractMin() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();
        const min = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.heapifyDown(0);
        return min;
    }

    // Method to heapify down the root value
    heapifyDown(index) {
        let smallest = index;
        const left = this.leftChildIndex(index);
        const right = this.rightChildIndex(index);

        if (left < this.heap.length && this.heap[left][0] < this.heap[smallest][0]) {
            smallest = left;
        }
        if (right < this.heap.length && this.heap[right][0] < this.heap[smallest][0]) {
            smallest = right;
        }
        if (smallest !== index) {
            [this.heap[smallest], this.heap[index]] = [this.heap[index], this.heap[smallest]];
            this.heapifyDown(smallest);
        }
    }

    // Method to check if the heap is empty
    isEmpty() {
        return this.heap.length === 0;
    }
}

/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    const minHeap = new MinHeap();
    
    // Push the head node of each list into the min-heap
    for (let i = 0; i < lists.length; i++) {
        if (lists[i]) {
            minHeap.insert([lists[i].val, i, lists[i]]);
        }
    }
    
    // Create a dummy head for the result linked list
    const dummy = new ListNode();
    let current = dummy;
    
    // While there are elements in the heap
    while (!minHeap.isEmpty()) {
        // Extract the smallest element from the heap
        const [val, i, node] = minHeap.extractMin();
        current.next = new ListNode(val);
        current = current.next;
        // If there is a next node in the same list, push it into the heap
        if (node.next) {
            minHeap.insert([node.next.val, i, node.next]);
        }
    }
    
    // Return the merged linked list
    return dummy.next;
};

Solution in Java:

Java

import java.util.PriorityQueue;

/**
 * Definition for singly-linked list.
 * public 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) {
        // Create a priority queue (min-heap)
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
        
        // Push the head node of each list into the priority queue
        for (ListNode node : lists) {
            if (node != null) {
                minHeap.add(node);
            }
        }
        
        // Create a dummy head for the result linked list
        ListNode dummy = new ListNode();
        ListNode current = dummy;
        
        // While there are elements in the priority queue
        while (!minHeap.isEmpty()) {
            // Extract the smallest element from the priority queue
            ListNode smallestNode = minHeap.poll();
            current.next = smallestNode;
            current = current.next;
            
            // If there is a next node in the same list, push it into the priority queue
            if (smallestNode.next != null) {
                minHeap.add(smallestNode.next);
            }
        }
        
        // Return the merged linked list
        return dummy.next;
    }
}

Solution in C#:

C#

using System.Collections.Generic;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */

public class Solution {
    public ListNode MergeKLists(ListNode[] lists) {
        // Edge case: if lists is null or empty, return null
        if (lists == null || lists.Length == 0) {
            return null;
        }
        
        // Define the priority queue (min-heap)
        SortedSet<(int, int, ListNode)> minHeap = new SortedSet<(int, int, ListNode)>(Comparer<(int, int, ListNode)>.Create((a, b) => {
            int result = a.Item1.CompareTo(b.Item1);
            if (result == 0) {
                result = a.Item2.CompareTo(b.Item2); // To handle duplicate values
            }
            return result;
        }));
        
        // Push the head node of each list into the priority queue
        for (int i = 0; i < lists.Length; i++) {
            if (lists[i] != null) {
                minHeap.Add((lists[i].val, i, lists[i]));
            }
        }
        
        // Create a dummy head for the result linked list
        ListNode dummy = new ListNode();
        ListNode current = dummy;
        
        // While there are elements in the priority queue
        while (minHeap.Count > 0) {
            // Extract the smallest element from the priority queue
            var smallest = minHeap.Min;
            minHeap.Remove(smallest);
            
            int val = smallest.Item1;
            int index = smallest.Item2;
            ListNode node = smallest.Item3;
            
            current.next = new ListNode(val);
            current = current.next;
            
            // If there is a next node in the same list, push it into the priority queue
            if (node.next != null) {
                minHeap.Add((node.next.val, index, node.next));
            }
        }
        
        // Return the merged linked list
        return dummy.next;
    }
}

23. Merge k Sorted Lists – Leetcode Solutions

Description:

Solution in Python:

Solution in Javascript:

Solution in Java:

Solution in C#:

Popular

313. Super Ugly Number – Leetcode Solutions

209. Minimum Size Subarray Sum – Leetcode Solutions

219. Contains Duplicate II – Leetcode Solutions

96. Unique Binary Search Trees – Leetcode Solutions

55. Jump Game – Leetcode Solutions

401. Binary Watch – Leetcode Solutions

The sys module in Python

23. Merge k Sorted Lists – Leetcode Solutions

Description:

Solution in Python:

Solution in Javascript:

Solution in Java:

Solution in C#:

Related Post

Popular