Merge k Sorted Lists

 

📌 Problem Idea

• You are given K sorted lists.

• You want to merge them into one final sorted list.

• Instead of merging two lists at a time (which can be slow), you use a min-heap to efficiently find the smallest element among all current nodes.

📚 Steps to Solve

1. Create a min-heap.

   • Each element of the heap will be a pointer to a node.

   • Heap is organized by node->data value (smallest data at top).

2. Insert the first node of each list into the heap.

3. While heap is not empty:

   • Extract the smallest node from the heap (this is the smallest value available).

   • Add this node to the result list.

   • If this extracted node has a next node, insert the next node into the heap.

4. Repeat until all nodes are processed.

🔥 Algorithm

Input: Array of K sorted linked list heads
Output: Single sorted linked list

1. Initialize an empty Min Heap.
2. For each list:
    If list is not empty:
        Insert its head node into the Min Heap.

3. Create a dummy head for the final sorted list.

4. While Min Heap is not empty:
    a. Extract the node with the smallest value.
    b. Add it to the result list.
    c. If the extracted node has a next node:
         Insert the next node into the Min Heap.

5. Return the next of dummy head (start of merged list).

🔥C Program
#include <stdio.h>
#include <stdlib.h>

#define MAX 100

// Structure of a linked list node
struct Node {
    int data;
    struct Node* next;
};

// Structure of heap node
struct HeapNode {
    struct Node* node;
};

// Min Heap structure
struct MinHeap {
    int size;
    struct HeapNode* arr[MAX];
};

// Function to create a new linked list node
struct Node* createNode(int data) {
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = data;
    temp->next = NULL;
    return temp;
}

// Function to swap two heap nodes
void swap(struct HeapNode** a, struct HeapNode** b) {
    struct HeapNode* temp = *a;
    *a = *b;
    *b = temp;
}

// Heapify (down) function
void heapifyDown(struct MinHeap* heap, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;

    if (left < heap->size && heap->arr[left]->node->data < heap->arr[smallest]->node->data)
        smallest = left;

    if (right < heap->size && heap->arr[right]->node->data < heap->arr[smallest]->node->data)
        smallest = right;

    if (smallest != idx) {
        swap(&heap->arr[smallest], &heap->arr[idx]);
        heapifyDown(heap, smallest);
    }
}

// Function to heapify up after inserting
void heapifyUp(struct MinHeap* heap, int idx) {
    if (idx == 0)
        return;

    int parent = (idx - 1) / 2;

    if (heap->arr[idx]->node->data < heap->arr[parent]->node->data) {
        swap(&heap->arr[idx], &heap->arr[parent]);
        heapifyUp(heap, parent);
    }
}

// Insert a node into heap
void insertHeap(struct MinHeap* heap, struct Node* node) {
    if (node == NULL)
        return;

    struct HeapNode* temp = (struct HeapNode*)malloc(sizeof(struct HeapNode));
    temp->node = node;
    heap->arr[heap->size] = temp;
    heapifyUp(heap, heap->size);
    heap->size++;
}

// Extract the minimum node from heap
struct Node* extractMin(struct MinHeap* heap) {
    if (heap->size == 0)
        return NULL;

    struct Node* root = heap->arr[0]->node;

    heap->arr[0] = heap->arr[heap->size - 1];
    heap->size--;
    heapifyDown(heap, 0);

    return root;
}

// Function to merge K sorted linked lists
struct Node* mergeKLists(struct Node* arr[], int k) {
    struct MinHeap heap;
    heap.size = 0;

    // Insert first node of each list into heap
    for (int i = 0; i < k; i++) {
        if (arr[i] != NULL)
            insertHeap(&heap, arr[i]);
    }

    // Dummy head for the result list
    struct Node* result = NULL, *last = NULL;

    while (heap.size > 0) {
        // Extract the minimum node
        struct Node* temp = extractMin(&heap);

        if (result == NULL) {
            result = temp;
            last = temp;
        } else {
            last->next = temp;
            last = last->next;
        }

        // Insert the next node from extracted node's list
        if (temp->next != NULL) {
            insertHeap(&heap, temp->next);
        }
    }

    return result;
}

// Function to print linked list
void printList(struct Node* head) {
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}

// Helper function to create a linked list from array
struct Node* createList(int arr[], int n) {
    struct Node* head = NULL, *temp = NULL;
    for (int i = 0; i < n; i++) {
        struct Node* newNode = createNode(arr[i]);
        if (head == NULL) {
            head = newNode;
            temp = head;
        } else {
            temp->next = newNode;
            temp = temp->next;
        }
    }
    return head;
}

// Main function
int main() {
    int k = 3; // Number of linked lists

    // Creating sample linked lists
    int arr1[] = {1, 4, 5};
    int arr2[] = {1, 3, 4};
    int arr3[] = {2, 6};

    struct Node* lists[k];

    lists[0] = createList(arr1, 3);
    lists[1] = createList(arr2, 3);
    lists[2] = createList(arr3, 2);
    printf("list A\n");
    printList(lists[0]);
    printf("list B\n");
    printList(lists[1]);
    printf("list C\n");
    printList(lists[2]);
    struct Node* result = mergeKLists(lists, k);
    
    printf("Merged Linked List:\n");
    printList(result);

    return 0;
}

Output

list A
1 4 5 
list B
1 3 4 
list C
2 6 
Merged Linked List:
1 1 2 3 4 4 5 6