Merge K sorted Linked Lists using Heap

 

🧩 Problem: Merge k Sorted Linked Lists

You are given k sorted linked lists.
Your task is to merge them into one sorted linked list efficiently.

⚙️ Naive Approach

• Concatenate all lists into one.

• Sort the combined list.
  ❌ Time Complexity: O(N log N)
  (where N = total number of nodes)

---

✅ Optimized Approach — Using a Min-Heap (Priority Queue)

Idea

• Maintain a min-heap containing the first node (smallest element) from each of the k lists.

• Repeatedly:

  1. Extract the minimum node from the heap.

  2. Append it to the result list.

  3. Insert the next node from the same list into the heap (if it exists).

This way, the smallest available element is always efficiently found in O(log k) time.

---

🧠 Algorithm

Input:

k sorted linked lists

Output:

A single sorted linked list

---

Steps:

1. Create a min-heap (using array or priority queue).

2. Insert the head node of each linked list into the heap (store value + pointer).

3. Initialize an empty result list (using dummy node).

4. While the heap is not empty:

   • Extract the smallest node (min).

   • Append it to the result list.

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

5. Return the merged list starting from dummy->next.

---

Complexity

• Each insertion and extraction in heap: O(log k)

• For all N nodes: O(N log k)

• Space: O(k) for heap

✅ C Program: Merge k Sorted Linked Lists Using Min-Heap

Note: This implementation assumes you know k and have created k sorted linked lists.You can modify the program to read k and also read k linked list in sorted order.

#include <stdio.h>

#include <stdlib.h>

#include <limits.h>

struct Node {

    int data;

    struct Node* next;

};

// Create new node

struct Node* newNode(int data) {

    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));

    temp->data = data;

    temp->next = NULL;

    return temp;

}

// Min-heap node: contains node pointer and list index

struct HeapNode {

    struct Node* node;

    int listIndex;

};

// Swap helper

void swap(struct HeapNode* a, struct HeapNode* b) {

    struct HeapNode temp = *a;

    *a = *b;

    *b = temp;

}

// Heapify down

void heapify(struct HeapNode heap[], int n, int i) {

    int smallest = i;

    int left = 2 * i + 1;

    int right = 2 * i + 2;

    if (left < n && heap[left].node->data < heap[smallest].node->data)

        smallest = left;

    if (right < n && heap[right].node->data < heap[smallest].node->data)

        smallest = right;

    if (smallest != i) {

        swap(&heap[i], &heap[smallest]);

        heapify(heap, n, smallest);

    }

}

// Build heap

void buildHeap(struct HeapNode heap[], int n) {

    for (int i = n / 2 - 1; i >= 0; i--)

        heapify(heap, n, i);

}

// Merge k sorted linked lists

struct Node* mergeKLists(struct Node* arr[], int k) {

    struct HeapNode* heap = (struct HeapNode*)malloc(sizeof(struct HeapNode) * k);

    int heapSize = 0;

    // Initialize heap with first node of each list

    for (int i = 0; i < k; i++) {

        if (arr[i] != NULL) {

            heap[heapSize].node = arr[i];

            heap[heapSize].listIndex = i;

            heapSize++;

        }

    }

    buildHeap(heap, heapSize);

    struct Node dummy;

    struct Node* tail = &dummy;

    dummy.next = NULL;

    while (heapSize > 0) {

        struct HeapNode root = heap[0];

        // Add smallest node to result

        tail->next = root.node;

        tail = tail->next;

        // Get next node from same list

        if (root.node->next != NULL) {

            heap[0].node = root.node->next;

        } else {

            heap[0] = heap[heapSize - 1];

            heapSize--;

        }

        heapify(heap, heapSize, 0);

    }

    return dummy.next;

}

// Display linked list

void printList(struct Node* node) {

    while (node != NULL) {

        printf("%d--> ", node->data);

        node = node->next;

    }

    printf("NULL\n");

}

// Example usage

int main() {

    int k = 3; // number of linked lists

    struct Node* arr[k];

    // List 1: 1 -> 4 -> 5

    arr[0] = newNode(1);

    arr[0]->next = newNode(4);

    arr[0]->next->next = newNode(5);

    arr[0]->next->next->next=NULL;

    printf("List1\n");

    printList(arr[0]);

    // List 2: 1 -> 3 -> 4

    arr[1] = newNode(1);

    arr[1]->next = newNode(3);

    arr[1]->next->next = newNode(4);

    arr[1]->next->next->next=NULL;

    printf("List2\n");

    printList(arr[1]);

    // List 3: 2 -> 6

    arr[2] = newNode(2);

    arr[2]->next = newNode(6);

    arr[2]->next->next=NULL;

    printf("List3\n");

    printList(arr[2]);

    struct Node* result = mergeKLists(arr, k);

    

    printf("Merged Sorted Linked List:\n");

    printList(result);

    return 0;

}

Output

List1

1--> 4--> 5--> NULL

List2

1--> 3--> 4--> NULL

List3

2--> 6--> NULL

Merged Sorted Linked List:

1--> 1--> 2--> 3--> 4--> 4--> 5--> 6--> NULL