Homework4

#include <iostream>

using namespace std;

struct Node
{
    int data;
    Node* next;
};

void Push(Node*& head, int element);
int sizell(Node* head);
void clear(Node*& head);
void printElements(Node* head);
void SortedInsert(Node*& head, int element);
void InsertSort(Node*& head);


int main()
{
    Node* llist = nullptr;
    int n, num;
    cout << "Enter number of elements: ";
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> num;
        Push(llist, num);
    }
    cout << "Before sort: ";
    printElements(llist);
    InsertSort(llist);
    cout << "After sort: ";
    printElements(llist);
    return 0;
}

void InsertSort(Node*& head)
{
    Node* sorted = nullptr;
    Node* current = head;
    while (current != nullptr)
    {
        SortedInsert(sorted, current->data);
        current = current->next;
    }
    clear(head);
    head = sorted;
}

void SortedInsert(Node*& head, int element)
{
    if (head == nullptr || head->data > element)
    {
        Node* n = new Node();
        n->data = element;
        n->next = head;
        head = n;
    }
    else
    {
        Node* current = head;
        while (current->next != nullptr && current->next->data < element)
        {
            current = current->next;
        }
        Node* n = new Node();
        n->data = element;
        n->next = current->next;
        current->next = n;
    }
}


void removeFirst(Node*& head)
{
    Node* current = head;
    head = head->next;
    delete current;
}

void Push(Node*& head, int element)
{
    Node* n = new Node();
    n->data = element;
    n->next = head;
    head = n;
}

int sizell(Node* head)
{
    int count = 0;
    Node* current = head;
    while (current != nullptr)
    {
        count++;
        current = current->next;
    }
    return count;
}

void printElements(Node* head)
{
    Node* current = head;
    while (current != nullptr)
    {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

void clear(Node*& head)
{
    Node* current = head;
    Node* prev = head;
    while (current != nullptr)
    {
        prev = current;
        current = current->next;
        delete prev;
    }
    head = nullptr;
}