#include <iostream>

using namespace std;
struct Node {
    int val;
    Node * next;

};

void add(Node *& H,int value)
{
    Node * p= new Node;
    p-> val=value;
    p->next=H;
    H=p;

}
void deleteFirst(Node *&H)
{
    if(H!= nullptr)
    {
        Node *p=H;
        H=H->next;
        delete p;
    }
}
void addNodeToEnd(Node *&head,Node *& tail , Node * e )
{
    e->next= nullptr;
    if(head== nullptr)
    {
        head=e;
        tail=e;
    } else
    {
        tail->next=e;
        tail=e;
    }

}
void swap(Node *& h)
{
    if(h!= nullptr&&h->next!= nullptr)
    {
        Node *p=h;
        h=p->next;
        p->next=h->next;
        h->next=p;
    }
}
void show_list_rek(Node * H)
{
    if(H!= nullptr)
    {
        cout<<H->val<<"->";
        if(H->next!= nullptr)
            show_list_rek(H->next);
        else cout<<"nullptr";
    }
}
void reverse(Node *&h)
{
    if(h!= nullptr)
    {
        Node* p=h;
        Node *h2= nullptr;
        while(p!= nullptr)
        {
            add(h2,p->val);
            p=p->next;
        }
        h=h2;

    }
}

void deleteAllWithOutMax(Node *&head) // OK działa dla wszystkich przypadków
{
    if(head)
    {
        int max=head->val;
        Node* p=head;
        while(p)
        {
            if(p->val>max)
            {
                max=p->val;
            }
            p=p->next;
        }
        Node* biggest= nullptr;
        add(biggest,max);
        head=biggest;

    }
}



//void avarage(Node *&head)
//{
//    if(head)
//    {
//        int sum=0;
//        int counter=0;
//        Node *p=head;
//        while(p)
//        {
//            sum+=p->val;
//            counter++;
//            p=p->next;
//        }
//       long double avearage = sum/counter;
//        Node * iterator= head;
//        Node *resoult= nullptr;
//        Node *tail= nullptr;
//        while (iterator)
//        {
//            if(iterator->val<avearage)
//            {
//                int value = iterator->val;
//                add(resoult,value);
//                deleteFirst(iterator);
//                iterator=iterator->next;
//            }
//
//            iterator=iterator->next;
//        }
//    }
//}
void avarage(Node *&head)
{
    int sum=0;
        int counter=0;
        Node *p=head;
        while(p)
        {
            sum+=p->val;
            counter++;
            p=p->next;
        }
       long double avarage = sum/counter;
        Node * below= nullptr;
        Node * above= nullptr;
        Node * iterator= head;
        while(iterator)
        {
            if(iterator->val<avarage)
            {
                add(below,iterator->val);

            }else add(above,iterator->val);
            iterator=iterator->next;
        }
    reverse(below);
        while(above)
        {
            add(below,above->val);
            above=above->next;
        }

        head=below;

}

void checkByPair(Node *&head)// test 1 -OK  dane wejściowe K ? OK
{
    if(head&&head->next)
    {
        Node *p=head;
        Node *pnext=head->next;
        Node *resoult= nullptr;
        while(p->next&&pnext->next)
        {
            if(p->val+pnext->val<0)
            {
                add(resoult,p->val);
                add(resoult,pnext->val);
                add(resoult,p->val);
                add(resoult,pnext->val);
            } else if(p->val+p->next->val>0)
            {

            } else {
                add(resoult,p->val);
                add(resoult,pnext->val);
            }
            p=p->next->next;
            pnext=pnext->next->next;
        }
        if(p== nullptr)
        {
            head=resoult;
        }else
        {
            add(resoult,p->val);
            head=resoult;
        }


    }
}


void insert(Node *&head,int val) // nie skonczona
{
    if(head)
    {
        Node *p=head;

        while(p&&p->next&&p->val<val){
            p=p->next;
            }
        if(p->next== nullptr)
        {
            Node *e=new Node();
            e->val=val;
            addNodeToEnd(head,p,e);


        }else{
            // tutaj dodać element w środku ;
            Node *e=new Node();
            e->val=val;
            e->next=p->next->next;
            p->next=e;



        }


    }else add(head,val);
}

void split (Node *& head,Node *& min,Node *&max,int x)
{

    Node * p=head;
    while(p)
    {
        if(p->val<x)
        {
            add(min,p->val);
        }else if(p->val>=x) {
            add(max,p->val);
        }
        deleteFirst(p);
    }
    head= nullptr;


}





int main()
{
    Node * head= nullptr;
    for(int i =7;i>-5;i-=2)
    {
        add(head,i);
    }
    show_list_rek(head);
    cout<<endl;
    show_list_rek(head);
    checkByPair(head);
    cout<<endl;
    show_list_rek(head);
    Node *zadanie2= nullptr;
    add(zadanie2,3);
    add(zadanie2,1);
    add(zadanie2,-8);
    add(zadanie2,7);
    add(zadanie2,3);
    add(zadanie2,2);
    add(zadanie2,-5);
    add(zadanie2,5);
    add(zadanie2,1);

    checkByPair(zadanie2);
    cout<<endl;
    show_list_rek(zadanie2);
    cout<<endl;



    Node * zadanie3= nullptr;
    add(zadanie3,7);
    add(zadanie3,8);
    add(zadanie3,2);
    add(zadanie3,23);
    add(zadanie3,7);
    add(zadanie3,3);
    avarage(zadanie3);
    show_list_rek(zadanie3);
    cout<<endl;

    Node * tab1= nullptr;
    Node *tab2= nullptr;
    Node *glowna=nullptr;
    add(glowna,2);
    add(glowna,3);
    add(glowna,6);
    add(glowna,7);
    add(glowna,8);
    split(glowna,tab1,tab2,5);
    show_list_rek(glowna);
    cout<<endl;
    show_list_rek(tab1);
    cout<<endl;
    show_list_rek(tab2);
    cout<<endl;

    Node * tablica= nullptr;
    insert(tablica,3);
    insert(tablica,5);
    insert(tablica,2);
    show_list_rek(tablica);





    return 0;
}