Sort List - C Solution

1. Introduction

This blog post addresses an essential problem in data structures using C programming: sorting a singly linked list in ascending order. Sorting a linked list is a fundamental task in many applications, from database management to algorithm design, and it tests one's understanding of linked list manipulation and sorting algorithms.

Problem

Given the head of a singly linked list, the objective is to sort the list in ascending order and return the head of the sorted list. The challenge involves efficiently reordering the nodes of the list without creating any new nodes.

2. Solution Steps

1. Find the middle of the linked list using the fast and slow pointer technique.

2. Divide the list into two halves.

3. Recursively sort each half.

4. Merge the two sorted halves.

5. Return the head of the sorted list.

3. Code Program

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

// Definition for singly-linked list.
struct ListNode {
    int val;
    struct ListNode *next;
};

// Function to merge two sorted linked lists
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    if (!l1) return l2;
    if (!l2) return l1;

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

// Function to sort a linked list
struct ListNode* sortList(struct ListNode* head) {
    if (!head || !head->next) return head;

    // Find the middle of the list
    struct ListNode *slow = head, *fast = head, *prev = NULL;
    while (fast && fast->next) {
        prev = slow;
        slow = slow->next;
        fast = fast->next->next;
    }
    prev->next = NULL; // Split the list into two halves

    // Sort each half and merge them
    struct ListNode *l1 = sortList(head);
    struct ListNode *l2 = sortList(slow);

    return mergeTwoLists(l1, l2);
}

// Utility function to create a new node
struct ListNode* newNode(int val) {
    struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

// Main function to demonstrate sortList function
int main() {
    // Create a sample list: 4->2->1->3
    struct ListNode* head = newNode(4);
    head->next = newNode(2);
    head->next->next = newNode(1);
    head->next->next->next = newNode(3);

    head = sortList(head); // Sort the list

    // Print the sorted list
    printf("Output: ");
    while (head != NULL) {
        printf("%d ", head->val);
        struct ListNode* temp = head;
        head = head->next;
        free(temp); // Free the node after printing
    }
    printf("\n");

    return 0;
}

Output:

1 2 3 4

Explanation:

The program sorts a linked list using the merge sort algorithm, which is efficient and suitable for linked lists. 

It first finds the middle of the list to divide it into two halves, then sorts each half recursively. 

Finally, it merges the two sorted halves to form a single sorted list. 

In the example, the list 4->2->1->3 is sorted to become 1->2->3->4. 

This method efficiently sorts the list in ascending order without using additional space for new nodes, demonstrating an effective application of the divide-and-conquer strategy in linked list operations.