Example: Linked List Insertion Sort in C++

// Linked List Insertion Sort
#include <iostream>
#include <cstddef> // For NULL

using namespace std;

// Node structure for the linked list
struct Node {
    int data;
    Node* next;

    Node(int val) : data(val), next(NULL) {}
};

// Function to insert a new node into a sorted list
Node* sortedInsert(Node* sortedHead, Node* newNode) {
    // Case 1: If sorted list is empty or newNode's data is smaller than head
    if (sortedHead == NULL || newNode->data <= sortedHead->data) {
        newNode->next = sortedHead;
        return newNode;
    } else {
        // Case 2: Traverse the sorted list to find the correct position
        Node* current = sortedHead;
        while (current->next != NULL && current->next->data < newNode->data) {
            current = current->next;
        }
        newNode->next = current->next;
        current->next = newNode;
        return sortedHead; // Head remains the same
    }
}

// Function to sort a linked list using Insertion Sort
Node* insertionSort(Node* head) {
    Node* sortedHead = NULL; // Head of the sorted list
    Node* current = head;    // Pointer to traverse the original list

    while (current != NULL) {
        Node* nextNode = current->next; // Store next node before modifying current
        sortedHead = sortedInsert(sortedHead, current);
        current = nextNode;
    }
    return sortedHead;
}

// Function to print the linked list
void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL" << endl;
}

int main() {
    // Step 1: Create an unsorted linked list
    Node* head = new Node(5);
    head->next = new Node(2);
    head->next->next = new Node(8);
    head->next->next->next = new Node(1);
    head->next->next->next->next = new Node(4);

    cout << "Original list: ";
    printList(head);

    // Step 2: Sort the linked list using Insertion Sort
    head = insertionSort(head);

    cout << "Sorted list (Insertion Sort): ";
    printList(head);

    // Step 3: Clean up memory (Important for linked lists)
    while (head != NULL) {
        Node* temp = head;
        head = head->next;
        delete temp;
    }

    return 0;
}