Merge K sorted Linked Lists

Given k sorted linked lists, the task is to merge them into one sorted linked list.

Input-Output Examples

Example 1:

  • Input:
    • List1: 1 -> 4 -> 5 -> NULL
    • List2: 1 -> 3 -> 4 -> NULL
    • List3: 2 -> 6 -> NULL
  • Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> NULL

Example 2:

  • Input:
    • List1: NULL
    • List2: NULL
    • List3: NULL
  • Output: NULL

Approach:

To merge k sorted linked lists efficiently, we can use a min-heap (priority queue). This allows us to always extract the smallest element among the k lists and maintain the sorted order.

Steps to implement:

  1. Initialize the Min-Heap:
    • Insert the head of each list into the min-heap.
  2. Merge the Lists:
    • Extract the smallest element from the min-heap.
    • Append it to the merged list.
    • If the extracted element has a next node, insert the next node into the min-heap.
    • Repeat until the min-heap is empty.

C++ Program to Merge K sorted Linked Lists

cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// Comparator for the priority queue
struct compare {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val;
    }
};

// Function to merge k sorted linked lists
ListNode* mergeKLists(vector<ListNode*>& lists) {
    priority_queue<ListNode*, vector<ListNode*>, compare> pq;

    // Insert the head of each list into the min-heap
    for (auto list : lists) {
        if (list) pq.push(list);
    }

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

    // Merge the lists
    while (!pq.empty()) {
        ListNode* temp = pq.top();
        pq.pop();
        current->next = temp;
        current = current->next;
        if (temp->next) pq.push(temp->next);
    }

    return dummy.next;
}

// Helper function to print the linked list
void printList(ListNode* head) {
    while (head != NULL) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "NULL" << endl;
}

int main() {
    // Creating 3 sorted linked lists
    ListNode* list1 = new ListNode(1);
    list1->next = new ListNode(4);
    list1->next->next = new ListNode(5);

    ListNode* list2 = new ListNode(1);
    list2->next = new ListNode(3);
    list2->next->next = new ListNode(4);

    ListNode* list3 = new ListNode(2);
    list3->next = new ListNode(6);

    vector<ListNode*> lists = {list1, list2, list3};

    // Merge the k sorted linked lists
    ListNode* result = mergeKLists(lists);
    cout << "Merged list: ";
    printList(result);

    return 0;
}

Java Program to Merge K sorted Linked Lists

java
import java.util.PriorityQueue;

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

public class Main {
    // Comparator for the priority queue
    public static class ListNodeComparator implements java.util.Comparator<ListNode> {
        public int compare(ListNode a, ListNode b) {
            return a.val - b.val;
        }
    }

    // Function to merge k sorted linked lists
    public static ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new ListNodeComparator());

        // Insert the head of each list into the min-heap
        for (ListNode list : lists) {
            if (list != null) pq.add(list);
        }

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

        // Merge the lists
        while (!pq.isEmpty()) {
            ListNode temp = pq.poll();
            current.next = temp;
            current = current.next;
            if (temp.next != null) pq.add(temp.next);
        }

        return dummy.next;
    }
    
    // Helper function to print the linked list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " -> ");
            head = head.next;
        }
        System.out.println("NULL");
    }

    public static void main(String[] args) {
        // Creating 3 sorted linked lists
        ListNode list1 = new ListNode(1);
        list1.next = new ListNode(4);
        list1.next.next = new ListNode(5);

        ListNode list2 = new ListNode(1);
        list2.next = new ListNode(3);
        list2.next.next = new ListNode(4);

        ListNode list3 = new ListNode(2);
        list3.next = new ListNode(6);

        ListNode[] lists = {list1, list2, list3};

        // Merge the k sorted linked lists
        ListNode result = mergeKLists(lists);
        System.out.print("Merged list: ");
        printList(result);
    }
}

Python Program to Merge K sorted Linked Lists

python
import heapq

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

# Comparator for the priority queue
ListNode.__lt__ = lambda self, other: self.val < other.val

# Function to merge k sorted linked lists
def merge_k_lists(lists):
    pq = []

    # Insert the head of each list into the min-heap
    for node in lists:
        if node:
            heapq.heappush(pq, node)

    dummy = ListNode(0)
    current = dummy

    # Merge the lists
    while pq:
        temp = heapq.heappop(pq)
        current.next = temp
        current = current.next
        if temp.next:
            heapq.heappush(pq, temp.next)

    return dummy.next

# Helper function to print the linked list
def print_list(head):
    while head:
        print(head.val, end=" -> ")
        head = head.next
    print("NULL")

# Creating 3 sorted linked lists
list1 = ListNode(1)
list1.next = ListNode(4)
list1.next.next = ListNode(5)

list2 = ListNode(1)
list2.next = ListNode(3)
list2.next.next = ListNode(4)

list3 = ListNode(2)
list3.next = ListNode(6)

lists = [list1, list2, list3]

# Merge the k sorted linked lists
result = merge_k_lists(lists)
print("Merged list:", end=" ")
print_list(result)

Merging k sorted linked lists can be efficiently handled by using a min-heap (priority queue). This approach ensures that we always extract the smallest element among the k lists, maintaining the sorted order.

DSA

8273

302

Related Articles