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.

⚙️ 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

📚 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 Implementation
#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