Merge K Sorted Linked Lists - Leetcode Solution

Problem Link

💡 Step-by-Step Thought Process

Understand the problem: Merge k sorted linked lists into one sorted linked list.
Initialize a min-heap to store nodes from the linked lists, using each node's value and index for ordering.
Iterate through the input lists, pushing each non-null head node onto the heap with its value and list index.
Create a dummy node to build the merged list, and set a current pointer to it.
While the heap is not empty, pop the node with the smallest value.
Attach the popped node to the current pointer's next, and move the current pointer forward.
If the popped node has a next node, push the next node onto the heap with its value and the same list index.
Return the next node of the dummy node as the head of the merged list.

Code 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, node in enumerate(lists):
            if node:
                heapq.heappush(heap, (node.val, i, node))
        
        D = ListNode()
        cur = D
        
        # n log k
        while heap:
            val, i, node = heapq.heappop(heap)
            cur.next = node
            cur = node
            node = node.next
            if node:
                heapq.heappush(heap, (node.val, i, node))
        
        return D.next
        # Time: O(N log K)
        # Space: O(K)

#include <vector>
#include <queue>
#include <functional>
using namespace std;


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)> minHeap(cmp);

        // Add the initial nodes of each list to the heap
        for (ListNode* node : lists) {
            if (node) {
                minHeap.push(node);
            }
        }

        ListNode dummy(0);
        ListNode* cur = &dummy;

        while (!minHeap.empty()) {
            ListNode* node = minHeap.top();
            minHeap.pop();
            cur->next = node;
            cur = node;
            if (node->next) {
                minHeap.push(node->next);
            }
        }

        return dummy.next;
    }
};

import java.util.PriorityQueue;


public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));

        // Add the initial nodes of each list to the heap
        for (ListNode node : lists) {
            if (node != null) {
                minHeap.offer(node);
            }
        }

        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;

        while (!minHeap.isEmpty()) {
            ListNode node = minHeap.poll();
            cur.next = node;
            cur = node;
            if (node.next != null) {
                minHeap.offer(node.next);
            }
        }

        return dummy.next;
    }
}

var mergeKLists = function(lists) {
    const heap = new MinHeap((a, b) => a.val - b.val);

    // Add the initial nodes of each list to the heap
    for (let node of lists) {
        if (node) {
            heap.push(node);
        }
    }

    let dummy = new ListNode(0);
    let cur = dummy;

    while (heap.size() > 0) {
        let node = heap.pop();
        cur.next = node;
        cur = node;
        if (node.next) {
            heap.push(node.next);
        }
    }

    return dummy.next;
};

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

    push(item) {
        this.heap.push(item);
        this.bubbleUp(this.heap.length - 1);
    }

    pop() {
        const top = this.heap[0];
        const end = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = end;
            this.bubbleDown(0);
        }
        return top;
    }

    size() {
        return this.heap.length;
    }

    bubbleUp(index) {
        const item = this.heap[index];
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            const parent = this.heap[parentIndex];
            if (this.compare(item, parent) >= 0) break;
            this.heap[index] = parent;
            index = parentIndex;
        }
        this.heap[index] = item;
    }

    bubbleDown(index) {
        const length = this.heap.length;
        const item = this.heap[index];
        while (true) {
            const leftChildIndex = 2 * index + 1;
            const rightChildIndex = 2 * index + 2;
            let swap = null;
            if (leftChildIndex < length) {
                const leftChild = this.heap[leftChildIndex];
                if (this.compare(leftChild, item) < 0) {
                    swap = leftChildIndex;
                }
            }
            if (rightChildIndex < length) {
                const rightChild = this.heap[rightChildIndex];
                if ((swap === null && this.compare(rightChild, item) < 0) ||
                    (swap !== null && this.compare(rightChild, this.heap[swap]) < 0)) {
                    swap = rightChildIndex;
                }
            }
            if (swap === null) break;
            this.heap[index] = this.heap[swap];
            index = swap;
        }
        this.heap[index] = item;
    }
}

Detailed Explanation

Understanding the Problem: Merge K Sorted Linked Lists

The “Merge K Sorted Linked Lists” problem challenges us to combine multiple sorted linked lists into a single sorted list. This is a common problem in systems that deal with merging data streams, merging multiple sorted files, or implementing external sorting in databases.

Each of the k input linked lists is already sorted in ascending order. The output should also be sorted, and the original node objects must be reused, not copied or rebuilt. This makes the problem slightly more complex than merging arrays.

Brute-Force Strategy: Using a Min Heap

A widely accepted approach to this problem uses a min heap (priority queue). The idea is to always have the smallest node available at the top of the heap. Here's how it works:

First, we push the head of each non-null linked list into the heap. Since each node contains a value and a pointer to the next node, we can extract the smallest value node efficiently using the heap's pop operation. Once popped, this node is appended to the result list, and if it has a next node, we push that next node into the heap.

This process continues until the heap is empty. Since the heap always contains the next smallest available node, the result list will be correctly sorted.

Efficiency Analysis

The time complexity of this approach is O(N log k), where:

N is the total number of nodes across all linked lists.
k is the number of linked lists.

Each node is inserted and removed from the heap exactly once, and each operation takes O(log k) time.

The space complexity is O(k) for storing up to k nodes in the heap at any point in time.

Alternative Approaches

Another common method is to use the Divide and Conquer technique. You recursively divide the list of linked lists into halves, merge each pair using a standard merge operation for two sorted lists, and combine the results. This approach also has a time complexity of O(N log k) and is often more memory-efficient in languages with heavier heap implementations.

Conclusion

The “Merge K Sorted Linked Lists” problem is a perfect example of applying data structures like heaps to simplify complex merging operations. Whether you use a min heap or divide and conquer, both solutions scale well and highlight the power of combining algorithmic techniques with clever data structure choices.

Get Personalized Support at AlgoMap Bootcamp 💡