#include <bits/stdc++.h>
using namespace std;

struct node{
    int val;
    node* next;
};

node* getTail(node* head){
    while(head != nullptr and head->next != nullptr)
        head = head->next;
    return head;
}

node* partition(node* head, node* end, node** newHead, node** newEnd){

    node* pivot = end;
    node *prev = nullptr, *cur = head, *tail = pivot;

    while(cur != pivot){
        if(cur->val < pivot->val){
            if(*newHead == nullptr)
                *newHead = cur;

            prev = cur;
            cur = cur->next;
        }
        else{
            if(prev)
                prev->next = cur->next;
            node* tmp = cur->next;
            cur->next = nullptr;
            tail->next = cur;
            tail = cur;
            cur = tmp;
        }
    }
    if(*newHead == nullptr)
        *newHead = pivot;

    *newEnd = tail;

    return pivot;
}

node* quicksortRec(node* head, node* end){

    if(!head or head==end)
        return head;

    node *newHead = nullptr, *newEnd = nullptr;
    node* pivot = partition(head, end, &newHead, &newEnd);

    if(newHead != pivot){
        node *tmp = newHead;
        while(tmp->next != pivot)
            tmp = tmp->next;
        tmp->next = nullptr;

        newHead = quicksortRec(newHead, tmp);

        tmp = getTail(newHead);
        tmp->next = pivot;

    }

    pivot->next = quicksortRec(pivot->next, newEnd);

    return newHead;
}

void quicksort(node** head){
    *head = quicksortRec(*head, getTail(*head));
    return;
}

void push(node* &head, int key){
    node* tmp = new node;
    tmp->val = key;
    tmp->next = head;
    head = tmp;
}

void push_back(node* &head, int key){
    node* p = new node;
    p->val = key;
    p->next = nullptr;
    if(head == nullptr){
        head = p;
        return;
    }
    node* tmp = head;
    while(tmp->next != nullptr)
        tmp=tmp->next;

    tmp->next = p;
}


node* reverse(node* list) {

    node* prev = nullptr;
    node* curr = list;
    node* next = nullptr;
    while(curr != nullptr){
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

void printL(node* head){
    while(head != nullptr){
        cout << head->val << "->";
        head=head->next;
    }
}

void swap(node* head, node* one, node* two){

    node* prev1 = head;
    node* prev2 = head;
    while(prev1->next != one)
        prev1=prev1->next;
    while(prev2->next != two)
        prev2=prev2->next;
    node* tmp = one->next;
    one->next = two->next;
    two->next = tmp;
    prev1->next = two;
    prev2->next = one;
}

int main(){
    node* list = new node;
    list->val = 10;
    list->next = nullptr;

    push(list, 11);
    push(list, 7);
    push(list, 8);
    node* p1 = list;
    push(list, 1);
    push(list, 4);
    push(list, 3);
    node* p2 = list;
    push(list, 5);
    push_back(list, 50);

    printL(list);
    swap(list, p1, p2);
    cout<<"\n";
    printL(list);

    list = reverse(list);

    cout << "\n";

    printL(list);
    quicksort(&list);
    cout << "\n";
    printL(list);
    return 0;
}