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 Nth node from the end of a singly linked list.
Next: C Programming Exercises, Practice, Solution : Linked List
What is the difficulty level of this exercise?
- Weekly Trends
- Python Interview Questions and Answers: Comprehensive Guide
- Scala Exercises, Practice, Solution
- Kotlin Exercises practice with solution
- MongoDB Exercises, Practice, Solution
- SQL Exercises, Practice, Solution - JOINS
- Java Basic Programming Exercises
- SQL Subqueries
- Adventureworks Database Exercises
- C# Sharp Basic Exercises
- SQL COUNT() with distinct
- JavaScript String Exercises
- JavaScript HTML Form Validation
- Java Collection Exercises
- SQL COUNT() function
- SQL Inner Join