#include <iostream>

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

bool broken(Node *a, Node *b, bool growing) {
    if (growing) return a->val > b->val;
    return a->val < b->val;
}

Node* insert(Node *head, Node *elem, bool growing) {
    if (head == nullptr || !broken(elem, head, growing)) {
        elem->next = head;
        return elem;
    }

    Node *p = head;
    while (p->next != nullptr && !broken(p->next, elem, growing))
        p = p->next;

    elem->next = p->next;
    p->next = elem;

    return head;
}

Node* fromArray(int t[], int n) {
    Node *head = new Node { nullptr, t[0] };
    Node *last = head;

    for (int i = 1; i < n; i++) {
        Node *tmp = new Node { nullptr, t[i] };
        last->next = tmp;
        last = tmp;
    }
    return head;
}

bool isGrowing(Node *L) {
    int numBigger = 0;
    Node *n = L;
    for (int i = 0; i < 3; i++) {
        if (n->val < n->next->val) numBigger++;
        else numBigger--;
        n = n->next;
    }

    return numBigger > 0;
}

Node* fixSortedList(Node *L) {
    // dla list dlugosci < 3 nie ma co sortowac
    if (L == nullptr || L->next == nullptr || L->next->next == nullptr) return L;

    // dla list dlugosci 3 wystarczy wsadzic te 3 wskazniki zeby posortowac wsio jak
    if (L->next->next->next == nullptr) {
        Node *n = insert(L->next->next, nullptr, false);
        n = insert(L->next, n, false);
        return insert(L, n, false);
    }

    // tu dochodzimy dla dlugosci wiekszej niz 3
    bool growing = isGrowing(L);

    Node *prevBig = nullptr;

    Node *p = L, *prev = nullptr;

    while (p->next != nullptr) {
        if (broken(p, p->next, growing)) {
            if (prevBig == nullptr) {
                prevBig = prev;
                break;
            }
        }

        prev = p;
        p = p->next;
    }

    if (prevBig == nullptr) return insert(L->next, L, growing);
    else {
        Node *big = prevBig->next;
        prevBig->next = big->next;
        return insert(L, big, growing);
    }
}


bool sorted(Node *head) {
    if (head == nullptr || head->next == nullptr) return true;
    return head->val < head->next->val && sorted(head->next);
}

void print(Node *n, bool first = true) {
    if (n == nullptr) return;
    std::cout << n->val << " ";
    print(n->next, false);
    if (first) std::cout << std::endl;
}

int main() {
    Node *n = fromArray(new int[5] {8, 3, 5, 4, 2}, 5);

    print(n);
    Node *nn = fixSortedList(n);
    print(nn);
}