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

typedef
  struct _list {
    int value;
    struct _list *next;
  }
  list;

#define NIL NULL

list* cons(int hd, list* tl) {
  list* node = malloc(sizeof(list));
  node->value=hd;
  node->next=tl;
  return node;
}

void destroy(list* tl) {
  if (tl) {
    destroy(tl->next);
    free(tl);
  }
}

void show_max(list* hd, int n) {
  if (hd==NULL)
    printf("nil\n");
  else if (n==0)
    printf("...\n");
  else {
    printf("%d,",hd->value);
    show_max(hd->next,n-1);
  }
}

void show(list* l) {
  show_max(l,-1);
}

int nth(int n, list* l) {
  if (n==0) return l->value;
  return nth(n-1,l->next);
}

int equals(list* l1, list* l2) {
  while (1) {
    if (l1==NULL) return (l2==NULL);
    if (l2==NULL) return 0;
    if (l1->value != l2->value) return 0;
    l1=l1->next;
    l2=l2->next;
  }
}

void glue_rec(list* l, list* tl) {
  if (l->next!=NULL)
   glue_rec(l->next,tl);
  else
    l->next = tl;
}

void glue(list* l, list* tl) {
  while (l->next!=NULL) l=l->next;
  l->next = tl;
}

void tie_rec(list* hd, list* tl) {
  if (tl->next)
    tie_rec(hd,tl->next);
  else
    tl->next=hd;
}

void tie(list* l) {
  list* tl=l;
  while(tl->next!=NULL)
    tl=tl->next;
  tl->next=l;
}

void untie(list* l) {
  list* tl=l;
  while (tl->next!=l) tl=tl->next;
  tl->next=NULL;
}

int is_circular(list* l) {
  list* a=l, *t=l;
  if (!a || !(a->next)) return 0;
  a=a->next;
  while (a!=t) {
    if (!a || !(a->next)) return 0;
    a = a->next->next;
    t = t->next;
  }
  return 1;
}

int main() {

  assert(1);
  assert(3);
  assert(!0);
  assert(!(1 & 2));
  assert(1 && 2);

  {
    list* l = cons(1,cons(2,cons(3,NIL)));
    printf("%d\n",nth(1,l));
    destroy(l);
    // printf("%d\n",nth(0,l));
  }

  {
    list* l1 = cons(1,cons(2,cons(3,NIL)));
    list* l2 = cons(4,cons(5,NIL));
    glue(l1,l2);
    show(l1);
    destroy(l1);
  }

  {
    list* l1 = cons(1,cons(2,cons(3,NIL)));
    list* l2 = cons(4,cons(5,NIL));
    list* l3 = cons(1,cons(2,cons(3,cons(4,cons(5,NIL)))));
    glue(l1,l2);
    assert(equals(l1,l3));
    assert(!equals(l2,l3));
    assert(!equals(l1,l2));
    assert(!equals(l1,NIL));
    destroy(l1);
    destroy(l3);
  }


  {
    list* l1 = cons(1,cons(2,cons(3,NIL)));
    list* l2 = cons(4,cons(5,NIL));
    glue(l1,l2);
    tie(l2);
    show_max(l1,20);
    untie(l2);
    destroy(l1);
  }

  {
    list* l1 = cons(1,cons(2,cons(3,NIL)));
    list* l2 = cons(4,cons(5,NIL));
    list* l3 = cons(7,NIL);
    assert(!is_circular(l1));
    assert(!is_circular(l2));
    assert(!is_circular(l3));
    assert(!is_circular(NIL));
    glue(l3,l1);
    printf("l1 circular: %d\n",is_circular(l1));
    glue(l1,l2);
    tie(l2);
    assert(is_circular(l1));
    assert(is_circular(l2));
    assert(is_circular(l3));
    printf("l1 circular: %d\n",is_circular(l1));
    untie(l2);
    destroy(l3);
  }

}