#include <iostream>
using std::cin;
using std::cout;
using std::endl;

class Node
{
public:
    int data;
    Node *next;
};

void insert(Node **head, Node *new_node)
{
    Node *curr;
    if (*head == NULL || (*head)->data >= new_node->data)
    {
        new_node->next = *head;
        *head = new_node;
    }
    else
    {
        curr = *head;
        while (curr->next != NULL && curr->next->data < new_node->data)
        {
            curr = curr->next;
        }
        new_node->next = curr->next;
        curr->next = new_node;
    }
}

void sort(Node **head)
{
    Node *sorted = NULL;
    Node *curr = *head;

    while (curr != NULL)
    {
        Node *next = curr->next;
        insert(&sorted, curr);
        curr = next;
    }
    *head = sorted;
}

//taken fron assignment 2/3
void enqueue(Node **head, int data)
{
    Node *new_node = new Node();

    new_node->data = data;
    new_node->next = *head;
    *head = new_node;
}

//also taken from assignment 2/3
int get(Node *head, int num)
{
    Node *cur = head;
    int count = 0;

    while (cur != NULL)
    {
        if (count == num)
        {
            return cur->data;
        }
        count++;
        cur = cur->next;
    }
}

//also also taken from assignment 2/3
void print_list(Node *node)
{
    while (node != NULL)
    {
        cout << node->data << ",";
        node = node->next;
    }
}

int main()
{
    Node *head = NULL;

    cout << endl
         << "Linked list: ";
    enqueue(&head, 47);
    enqueue(&head, 53);
    enqueue(&head, 77);
    enqueue(&head, 29);
    enqueue(&head, 81);
    enqueue(&head, 20);
    enqueue(&head, 99);
    enqueue(&head, 0);
    print_list(head);
    cout << endl;

    sort(&head);
    cout << endl
         << "Sorted linked list: ";
    print_list(head);

    cout << endl
         << endl
         << "Get element check (position 4): " << get(head, 4) << endl
         << endl;
}