competitive/abssortedlinkedlist.cpp at main · krishna-mathuria/competitive · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;

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

void push(Node** head, int data)
{
    Node* newNode = new Node;
    newNode->next = (*head);
    newNode->data = data;
    (*head) = newNode;
}


void printList(Node* head)
{
    while (head != NULL)
    {
        cout << head->data;
        if (head->next != NULL)
            cout << " -> ";
        head = head->next;
    }
    cout<<endl;
}

void sortList(Node** head){
     Node* prev = (*head);
    Node* curr = (*head)->next;

    while (curr != NULL)
    {

        if (curr->data < prev->data)
        {
            prev->next = curr->next;

            curr->next = (*head);
            (*head) = curr;

            curr = prev;
        }
        else
            prev = curr;

        curr = curr->next;
}

int main()
{
    Node* head = NULL;
    push(&head, -5);
    push(&head, 5);
    push(&head, 4);
    push(&head, 3);
    push(&head, -2);
    push(&head, 1);
    push(&head, 0);

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

    sortList(&head);

    cout << "\nSorted list :\n";
    printList(head);

    return 0;
}