#include <iostream.h>
#include<conio.h>
#include<stdio.h>
#include<string.h>

struct Num
{
    int n;
    struct Num *next;
};
Num *Start = NULL;
Num *Rear = NULL;

void Insert()
{
    Num *ptr = new Num;
    cout << "Enter number: ";
    cin >> ptr->n;
    ptr->next = NULL;
    if (Start == NULL)
        Start = Rear = ptr;
    else
    {
        Rear->next = ptr;
        Rear = ptr;
    }
}

void sortedList(struct Num **head, struct Num *newNum)
{
    struct Num *current;
    if (*head == NULL || (*head)->n >= newNum->n)
    {
        newNum->next = *head;
        *head = newNum;
    }
    else
    {
        // Locate the node before the point of insertion
        current = *head;
        while (current->next != NULL &&
               current->next->n < newNum->n)
        {
            current = current->next;
        }
        newNum->next = current->next;
        current->next = newNum;
    }
}

void InsertSort(Num **start)
{
    struct Num *sorted = NULL; // list to store the sorted list
    struct Num *current = *start;
    while (current != NULL)
    {
        struct Num *next = current->next;
        // insert current in sorted linked list
        sortedList(&sorted, current);
        current = next;
    }
    // new start points to the sorted list
    *start = sorted;
}

void Display()
{
    cout << "Sorted List:\n";
    Num *ptr = new Num;
    ptr = Start;
    while (ptr != NULL)
    {
        cout << ptr->n << "\t";
        ptr = ptr->next;
    }
}

int main()
{
    clrscr();
    cout << "Enter 10 values into the linked list:\n";
    for (int i = 0; i < 10; i++)
    {
        Insert();
    }
    InsertSort(&Start);
    Display();
    getch();
    return 0;
}

#include <iostream>
using namespace std;

struct Num
{
    int n;
    struct Num *next;
};
Num *Start = NULL;
Num *Rear = NULL;

void Insert()
{
    Num *ptr = new Num;
    cout << "Enter number: ";
    cin >> ptr->n;
    ptr->next = NULL;
    if (Start == NULL)
        Start = Rear = ptr;
    else
    {
        Rear->next = ptr;
        Rear = ptr;
    }
}

void sortedList(struct Num **head, struct Num *newNum)
{
    struct Num *current;
    if (*head == NULL || (*head)->n >= newNum->n)
    {
        newNum->next = *head;
        *head = newNum;
    }
    else
    {
        // Locate the node before the point of insertion
        current = *head;
        while (current->next != NULL &&
               current->next->n < newNum->n)
        {
            current = current->next;
        }
        newNum->next = current->next;
        current->next = newNum;
    }
}

void InsertSort(Num **start)
{
    struct Num *sorted = NULL; // list to store the sorted list
    struct Num *current = *start;
    while (current != NULL)
    {
        struct Num *next = current->next;
        // insert current in sorted linked list
        sortedList(&sorted, current);
        current = next;
    }
    // new start points to the sorted list
    *start = sorted;
}

void Display()
{
    cout << "Sorted List:\n";
    Num *ptr = new Num;
    ptr = Start;
    while (ptr != NULL)
    {
        cout << ptr->n << "\t";
        ptr = ptr->next;
    }
}

int main()
{
    cout << "Enter 10 values into the linked list:\n";
    for (int i = 0; i < 10; i++)
    {
        Insert();
    }
    InsertSort(&Start);
    Display();
    return 0;
}