#include <stdio.h>
#include <stdlib.h>

/*
linked list that countains 1 and 2:

* l --> [1 | ]
*           |
*           `-> [2 | ]
*                   |
*                   `-> NULL
*/

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

void list_init(Node **n)
{
  *n = NULL;
}

// before -> [1] -> [2] -> [3] -> NULL
// after -> [N] -> [1] -> ......

void list_push(int value, Node **head)
{
  Node *new_head = malloc(sizeof(Node));
  new_head->val = value;
  new_head->next = *head;
  *head = new_head;
}

void list_print(Node *head)
{
  for(; head; head = head->next)
    printf("%d\n", head->val);
}


void list_pop(Node **head) {
  Node *new_head = (*head)->next;
  free(*head);
  *head=new_head;
}


void list_clear (Node **head){
  while (*head){
    list_pop(head);
  }
}

//    p -> [1] -> [2] -> [3] -> NULL
// NULL <- [1] <- [2] <- [3] <- p

// from -> [1] -> [2] -> ...
// to  -> NULL
// temp -> [1] -> NULL.
// temp -> [1] -> [2]
// from -> [2] -> ...
// to  -> [1] -> [2] -> .....

void list_splice (Node **from, Node **to){
  Node *temp = *from;
  *from = temp->next;
  temp->next = *to;
  *to = temp;
}

void list_reverse (Node **head){
  Node *new_list = NULL;
  while (*head) {
    list_splice(head, &new_list);
  }
  *head = new_list;
}

void swap(int *a, int *b)
{
  int c=*a;
  *a=*b;
  *b=c;
}

void bubble_sort(Node *head)
{
  Node *i, *j;
  for(i = head; i; i = i->next){
    for(j = head; j->next; j =j->next){
      if(j->val > j->next->val) swap(&j->val, &j->next->val);
    }
  }
}

int main() {
  int x,y;
  swap(&x,&y);

  Node *list;
  list_init(&list);
  list_push(15, &list);
  list_push(6, &list);
  list_push(3, &list);
  list_push(4, &list);
  list_push(5, &list);
  list_print(list);
  list_pop(&list);
  list_print(list);
  list_reverse(&list);
  list_print(list);
  bubble_sort(list);
  list_print(list);
  list_clear(&list);
  return 0;
}