C Exercises: Combine k sorted linked lists into a single sorted linked list

C Singly Linked List : Exercise-29 with Solution

Write a C program to merge k sorted linked lists into a single sorted linked list.

Sample Solution:

C Code:

#include<stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

struct Node* newNode(int data) {
struct Node* temp = (struct Node*) malloc(sizeof(struct Node));
temp->data = data;
temp->next = NULL;
return temp;
}
// Function to display a linked list
void displayList(struct Node* head) {
    while (head) {
      printf("%d ", head->data);
     head = head->next;
    }
    printf("\n");
}
// Function to merge two sorted linked singly_lists into a single sorted linked list
struct Node* mergeTwoLists(struct Node* l1, struct Node* l2) {
    if (!l1) return l2;
    if (!l2) return l1;

    if (l1->data < l2->data) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}

struct Node* mergeKLists(struct Node** lists, int listsSize)
{
    if(listsSize == 0)
        return NULL;
    if(listsSize == 1)
        return lists[0];
    if(listsSize == 2)
        return mergeTwoLists(lists[0], lists[1]);

    int mid = listsSize / 2;
    struct Node *left = mergeKLists(lists, mid);
    struct Node *right = mergeKLists(lists + mid, listsSize - mid);

    return mergeTwoLists(left, right);
}


int main() {
int k = 3;
struct Node* singly_lists[2];

singly_lists[0] = newNode(10);
singly_lists[0]->next = newNode(20);
singly_lists[0]->next->next = newNode(50);
printf("List-1:\n");
displayList(singly_lists[0]);
singly_lists[1] = newNode(30);
singly_lists[1]->next = newNode(40);
singly_lists[1]->next->next = newNode(60);
printf("List-2:\n");
displayList(singly_lists[1]);
singly_lists[2] = newNode(10);
singly_lists[2]->next = newNode(70);
singly_lists[2]->next->next = newNode(100);
printf("List-3:\n");
displayList(singly_lists[2]);
struct Node* result = mergeKLists(singly_lists, k);
printf("\nAfter merging the said three sorted lists into one sorted list:\n");
displayList(result); 
return 0;
}

Sample Output:

List-1:
10 20 50 
List-2:
30 40 60 
List-3:
10 70 100 

After merging the said three sorted lists into one sorted list:
10 10 20 30 40 50 60 70 100 

Flowchart :

C Programming Code Editor:

Previous: Remove N^th node from the end of a singly linked list.
Next: C Programming Exercises, Practice, Solution : Linked List