#include <iostream>

using namespace std;

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

void Add(node*&H, int x)
{
  node* p = new node;
  p->val=x;
  p->next=H;
  H=p;
}
void del(node*&H)
{
  if(H!=NULL)
  {
    node*p = H;
    H=H->next;
    delete p;
  }
}
void show(node*H)
{
  node*p=H;
  while(p!=NULL)
  {
    cout<<p->val<<"->";
    p=p->next;
  }
  cout<<"NULL"<<endl;
}

int findmin(node*H)
{
  if(H!=NULL)
  {
  int min = 0;
  node *p = H;
  while(p!=NULL)
  {
    if(p->val <min)
    {
      min=p->val;
    }
    p=p->next;
  }

  }
}
void bubblesort(node *&H) {
    node *p = H;
    node *wstaw = NULL;
    int counter = 0;

    while (p) {
        counter++;
        p=p->next;
    }


    Add(H, findmin(H) - 1);
    p=H;
    for (int i = 0; i < counter; i++) {
        for (int j = 0; j < counter - 1; j++) {
            if (p->next->val > p->next->next->val) {
                wstaw = p->next;
                p->next = wstaw->next;
                wstaw->next = p->next->next;
                p->next->next = wstaw;
            }
            p = p->next;
        }
        p = H;
    }
    del(H);
show(H);

}

void insert(node *& H, int x)//wymaga aby lista byla posortowana
{
    node * pom = new node;//pomocniczy wskaźnik do skakania
    if (H == NULL)//jesli pusta lista to standardowo wstawiamy
    {
        Add(H, x);
    }
    else if (H->val > x)//jesli jest najmniejszy to także standardowo wstawiamy
    {
        Add(H, x);
    }
    else
    {
        pom = H;
        while (pom->next)
        {
            if (pom->next->val > x)// wstawianie jesli w środku
            {
                node * p = new node;
                node * pomocniczy = pom->next;
                p->val = x;
                pom->next = p;
                p->next = pomocniczy;
                return;
            }
            pom = pom->next;
        }
        //wstawianie jesli wskaznik idzie na koniec
        node * p = new node;
        node * pomocniczy = pom->next;
        p->val = x;
        pom->next = p;
        p->next = pomocniczy;



    }
del(H);
show(H);
}

int main()
{
    node* H = NULL;
  Add(H, 5);
  Add(H, 2);
   Add(H, 5);
  Add(H, 9);
   Add(H, 2);
  Add(H, 6);
   Add(H, 5);
  Add(H, 3);
   Add(H, 5);
  Add(H, 7);
   Add(H, 2);
  Add(H, 1);
 bubblesort(H);
  cout<<endl;

  insert(H,0);

    return 0;
}