C Exercises: Sort a singly linked list using merge sort

Last update on December 20 2024 13:06:10 (UTC/GMT +8 hours)

Write a C program to sort a singly linked list using merge sort.

Sample Solution:

C Code:

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

// Define a structure for a Node in a singly linked list
struct Node {
    int data;
    struct Node* next;
};

// Function to create a new node with given data
struct Node* new_Node(int data) {
    // Allocate memory for a new node
    struct Node* node = (struct Node*) malloc(sizeof(struct Node));
    // Set the data for the new node
    node->data = data;
    // Set the next pointer of the new node to NULL
    node->next = NULL;
    return node;
}

// Function to merge two sorted linked lists
struct Node* sorted_Merge(struct Node* x, struct Node* y) {
    struct Node* result = NULL;

    // Base cases for recursion
    if (!x)
        return y;
    if (!y)
        return x;

    // Pick either node from x or y, and continue merging
    if (x->data <= y->data) {
        result = x;
        result->next = sorted_Merge(x->next, y);
    } else {
        result = y;
        result->next = sorted_Merge(x, y->next);
    }
    return result;
}

// Function to find the middle of a linked list
struct Node* getMiddle(struct Node* head) {
    if (!head)
        return head;

    struct Node *slow = head, *fast = head;
    // Use slow and fast pointers to find the middle node
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// Function implementing the merge sort algorithm for linked list
struct Node* mergeSort(struct Node* head) {
    if (!head || !head->next)
        return head;

    // Split the linked list into two halves
    struct Node *middle = getMiddle(head);
    struct Node *nextOfMiddle = middle->next;
    middle->next = NULL;

    // Recursively sort the two halves
    struct Node *left = mergeSort(head);
    struct Node *right = mergeSort(nextOfMiddle);

    // Merge the sorted halves
    struct Node *sortedList = sorted_Merge(left, right);
    return sortedList;
}

// Function to display the elements of a linked list
void displayList(struct Node* head) {
    // Traverse the list and print each element
    while (head) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}

// Main function where the execution starts
int main() {
    // Create a singly linked list
    struct Node* list = new_Node(2);
    list->next = new_Node(3);
    list->next->next = new_Node(1);
    list->next->next->next = new_Node(7);
    list->next->next->next->next = new_Node(5);

    printf("Sort the said singly linked list using merge sort:\n");
    displayList(list); // Display the original list

    // Perform merge sort on the list
    struct Node* result = mergeSort(list);
    printf("\nAfter sorting the said list:\n");
    displayList(result); // Display the sorted list

    return 0; // Indicates successful completion of the program
}

Sample Output:

Sort the said singly linked list using merge sort:
2 3 1 7 5 

After sorting the said list:
1 2 3 5 7

Flowchart :

C Programming Code Editor:

Previous: Remove duplicates from a unsorted singly linked list.
Next: Copy of a singly linked list with random pointers.