#include <stdio.h>
#include <stdlib.h>
// Node structure
struct Node {
int data;
struct Node* next;
};
// Function to create a new node
struct Node* newNode(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->next = NULL;
return node;
}
// Function to split the linked list into two halves
void split(struct Node* source, struct Node** front, struct Node** back) {
struct Node* fast;
struct Node* slow;
slow = source;
fast = source->next;
// Move fast two nodes and slow one node
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
// Split the list
*front = source;
*back = slow->next;
slow->next = NULL;
}
// Function to merge two sorted linked lists
struct Node* merge(struct Node* a, struct Node* b) {
struct Node* result = NULL;
// Base cases
if (a == NULL) return b;
if (b == NULL) return a;
// Pick either a or b and recurse
if (a->data <= b->data) {
result = a;
result->next = merge(a->next, b);
} else {
result = b;
result->next = merge(a, b->next);
}
return result;
}
// Main merge sort function
void mergeSort(struct Node** headRef) {
struct Node* head = *headRef;
struct Node* a;
struct Node* b;
// Base case: if head is NULL or only one element
if (head == NULL || head->next == NULL) {
return;
}
// Split head into two halves
split(head, &a, &b);
// Recursively sort both halves
mergeSort(&a);
mergeSort(&b);
// Merge the sorted halves
*headRef = merge(a, b);
}
// Function to print the linked list
void printList(struct Node* node) {
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}
// Function to insert at the beginning
void push(struct Node** headRef, int data) {
struct Node* newNodePtr = newNode(data);
newNodePtr->next = *headRef;
*headRef = newNodePtr;
}
// Example usage
int main() {
struct Node* head = NULL;
// Create an unsorted linked list: 64 -> 34 -> 25 -> 12 -> 22 -> 11 -> 90
push(&head, 90);
push(&head, 11);
push(&head, 22);
push(&head, 12);
push(&head, 25);
push(&head, 34);
push(&head, 64);
printf("Original linked list: ");
printList(head);
// Sort the linked list
mergeSort(&head);
printf("Sorted linked list: ");
printList(head);
return 0;
}