Listy Jednostronnie wiązane

#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 swapSecond(Node *&head)
{
    if(head&&head->next)
    {
        swap(head);
        Node * p=head->next;
        while(p->next&&p->next->next)
        {
            swap(p->next);
            p=p->next->next;
        }
    }
}
void deleteEven(Node *&H)
{
    Node * head= nullptr;
    Node *p= H;
    int i=0;
    while(p!= nullptr)
    {
        if(i%2==0)
        add(head,p->val);
        i++;
        p= p->next;
    }
    H=head;
}

void multipleByTwo(Node *&h)
{
    if(h!= nullptr)
    {
        Node * head= nullptr;
        Node *p= h;
        while(p!= nullptr)
        {

            add(head,p->val);
            add(head,p->val);

            p= p->next;
        }
        show_list_rek(head);

    }
}
void multipleByValueNumber(Node *&h)
{
    if(h!= nullptr)
    {
        Node * head= nullptr;
        Node *p= h;
        while(p!= nullptr)
        {
            for(int i =0;i<p->val;i++)
            {
                add(head,p->val);
            }
            p= p->next;
        }
//        show_list_rek(head);
        h=head;
    }
}
void swapFirstWithSecond(Node* & head)
{
    if(head!= nullptr && head-> next != nullptr)
    {
        Node * forgotten=head;
        head=forgotten->next;
        forgotten->next=head->next;
        head->next=forgotten;
    }
}
void swapFirstWithLast(Node * & head)
{
    if(head!= nullptr)
    {
        Node * iterator=head;
        Node * headCopy=head;
        while(iterator!= nullptr)
            iterator=iterator->next;
        iterator->next=head->next;
        head->next=iterator;

    }


}
void swap2(Node *&H,Node *&replaced)
{
   if(H!= nullptr&&replaced!= nullptr)
   {
       Node *kopia_Glowy=H;
       Node *kopia_nastepnika_Glowy=kopia_Glowy->next;
       kopia_Glowy=replaced;
       replaced->next=kopia_nastepnika_Glowy;

   }
}

//void swap(Node *&H)
//{
//    if(H!= nullptr&&H->next!= nullptr)
//    {
//        Node *p=H;
//        H=p->next;
//        p->next=H->next;
//        H->next=p;
//    }
//}
void zamianaPierwszegoElementuZOstatnimNaLiscie(Node *&head)
{
    if(head!= nullptr)
    {
        Node *iterator=head;
        while(iterator->next!= nullptr)
        {
            cout<<iterator->val<<" ";
            iterator=iterator->next;

        }
        swap2(head,iterator->next);

    }

}


void replaceXWithHisNext ( Node *& head  ,int x)
{
    if(head!= nullptr&&head->next!= nullptr)
    {
        Node * n=head;
        if(head->val==x)
        {
            swap(head);
        }else
        {
            Node *p=head;
            while(p->next!= nullptr&&p->next->val!=x)
            {
                p=p->next;
            }
            if(p->next!= nullptr&&p->next->next!= nullptr)
            {
                Node *e=p->next;
                p->next=e->next;
                e->next=e->next->next;
                p->next->next=e;
            }
        }
    }
}





void replaceXWithHisPervious ( Node *& head  ,int x)
{
    if(head!= nullptr&&head->next!= nullptr)
    {
        Node * n=head;
        while(n->next!= nullptr)
        {
            if(n->next->val==x) {
                cout<<"\nZnalazlem"<<endl;
                Node * forgotten=n;
                n=forgotten->next;
                forgotten->next=n->next;
                n->next=forgotten;
                cout<<forgotten->val<<endl<<n->val<<endl;
                break;
            }
            else n=n->next;
        }
    }
}





void nextTryReplace(Node *&head,int x)
{
    if(head!= nullptr)
    {
        Node * p=head;
        if(head->next== nullptr)
        {
            return;
        }
        if(head->val==x)
        {
            return;
        }else while(p->next!= nullptr&&p->next->val!=x)
            {
            p=p->next;
            }
        if(p->next== nullptr)
        {
            return;
        } else
        {
            Node* copy= p;
            p->next;
            p=p->next;


        }


    }


}
//KUSTRA
void funkcja1(Node *&H)
{

}




void copy(Node *h)
{
    if(h)
    {
        Node *h2= nullptr;
        Node *p=h;
        while(p->next!= nullptr)
        {
            add(h2,p->val);
            p=p->next;
        }
        add(h2,p->val);
        p->next=h2;
        h2= nullptr;
    }

}
// zamienię miejscami całą tablicę
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;

    }
}


//podziele na pół
void split(Node *&h)
{
Node * p=h;
Node * copy= nullptr;
int i=0;
while(p) // policz liczbę elementów
{
    p=p->next;
    i++;
}
i/=2;
while(i!=0)
{
    i--;
    add(copy,h->val);
    h=h->next;
}
h=copy;

}
void split(Node *&h,Node *& first,Node *&second)
{
    Node * p=h;
    Node * iterator=h;
    first= nullptr;
    second = nullptr;
    int i=0;
    while(p!= nullptr) // policz liczbę elementów
    {
        p=p->next;
        i++;
    }
    i/=2;
    while(i!=0)
    {
        i--;
        add(first,iterator->val);
        iterator=iterator->next;
    }
    while(iterator!= nullptr)
    {
        add(second,iterator->val);
        iterator=iterator->next;
    }

}

void merge (Node *& head,Node *& first,Node *&second)
{
    //head= nullptr;
    //first = wartości
    //second = wartości
    //1) Głowy NIE RUSZAMY DO Glownej tablicy
    head= nullptr;
    Node * supporter1=first;
    Node * supporter2=second;
    while(supporter1||supporter2)
    {
        if(supporter1&&supporter2== nullptr)
        {
            add(head,supporter1->val);
            cout<<"pusty drugi"<<supporter1->val<<" ";
            supporter1=supporter1->next;
        }else
        if(supporter2&&supporter1== nullptr)
        {
            add(head,supporter2->val);
            cout<<"pusty pierwszy"<<supporter2->val<<" ";
            supporter2=supporter2->next;
        }else
        if(supporter1->val>=supporter2->val)
        {
            add(head,supporter1->val);
            cout<<"Pierwszy warunek pelny"<<supporter1->val<<" ";
            supporter1=supporter1->next;
        } else
        {
            add(head,supporter2->val);
            cout<<"warunek else"<<supporter2->val<<" ";
            supporter2=supporter2->next;
        }
    }
}

void bubleSort(Node *&head)//////////// nwm czy DB
{
    if(head)
    {
        Node * p=head;
        Node * e= nullptr;

        int i=0;
        bool czyzachodzizamiana= true;
        while(czyzachodzizamiana)
        {
            if(e==head) return;
            if(p==e)
            {
                p=head;
                continue;
            }
            if(p->val>p->next->val)
            {
                swap(p);
                e=p;

            }
            p=p->next;

        }
    }

}

//void swapNodes(Node*& head_ref,int numberOfPlacesAhead, int x, int y)
//{
//
//
//    // Search for x (keep track of prevX and CurrX
//    Node *prevX = NULL, *currX = head_ref;
//
//
//    // Search for y (keep track of prevY and CurrY
//    Node *prevY = NULL, *currY = head_ref;
//    while (currY && numberOfPlacesAhead!=0) {
//        prevY = currY;
//        currY = currY->next;
//        numberOfPlacesAhead--;
//    }
//
//    // If either x or y is not present, nothing to do
//    if (currX == NULL || currY == NULL)
//        return;
//
//    // If x is not head of linked list
//    if (prevX != NULL)
//        prevX->next = currY;
//    else // Else make y as new head
//        head_ref = currY;
//
//    // If y is not head of linked list
//    if (prevY != NULL)
//        prevY->next = currX;
//    else // Else make x as new head
//        head_ref = currX;
//
//    // Swap next pointers
//    Node* temp = currY->next;
//    currY->next = currX->next;
//    currX->next = temp;
//}

void sortowanieGrzebieniowe(Node *&head)
{
    if(head)
    {
        if(head->next== nullptr)///jednoelementowa tablica
        {
            return;
        } else
        {
            int licznik=0;
            Node * p=head;
            while(p) // liczę ilość elementów w tablicy
            {
                licznik++;
                p=p->next;
            }
            int gap = licznik/1.3;

            add(head,0);//fake element
for(;gap!=1;gap=gap/1.3)
{
    int gapCopy=gap-1;
    Node* iterator=head;//szukamy poprzednika tej listy
    Node* iterator2=head;
    while(iterator&&gapCopy!=0)
    {
        iterator=iterator->next;
        gapCopy--;
    }

            while(iterator!= nullptr)
            {

                if(iterator->val>iterator2->val)
                {
                    iterator->next=iterator2->next;
                    iterator2->next=iterator;
                }
                iterator=iterator->next;
                iterator2=iterator2->next;
            }

    if(gap==1)
    {
        //bublesort
        return;
    }


        }

    }
}

}

int main() {

    Node * h= nullptr;
    Node * first= nullptr;
    Node * second= nullptr;
    add(h,3);
    sortowanieGrzebieniowe(h);






    return 0;
}