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

#define new(type, size) (type*)malloc(sizeof(type)*(size))

typedef struct List {
  int car;           //  Data
  struct List* cdr;  //  Tail
} List;

List* newList(int Data) {
  List* Head = new(List, 1);
  Head->car = Data;
  Head->cdr = NULL;
  return Head;
}

void destroy(List* Head) {
// This function has risk that this can make dangling pointer.
  List* cdr = Head->cdr;
  while(cdr) {
    free(Head);
    Head = cdr;
    cdr = cdr->cdr;
  }
}

void printList(List* Head) {
  List* tmp = Head;
  printf("[");
  while(tmp) {
    printf("%d, ", tmp->car);
    tmp = tmp->cdr;
  }
  printf("\b]\n");
}

void append(List* Head, int Data) {
  List* tmp = Head;
  while(tmp->cdr) {
    tmp = tmp->cdr;
  }
  tmp->cdr = new(List, 1);
  tmp = tmp->cdr;
  tmp->car = Data;
  tmp->cdr = NULL;
}

//nth node of list
List* nth_cdr(List* Head, int idx) {
  int i;
  List* tmp = Head;
  for (i = 0; i < idx; i++) {
    if (!tmp->cdr) return tmp;
    tmp = tmp->cdr;
  }
  return tmp;
}

// loop checking function
int loop_existence(List* Head) {
  List* tmp = Head;
  int count=0;
  while(tmp) {
    List* tmp2 = Head;
    int count2 = 0;
    while(tmp!=tmp2) {
      tmp2=tmp2->cdr;
      count2++;
    }
    if (count!=count2) return 1;
    tmp=tmp->cdr;
    count++;
  }
  return 0;
}

int main(void) {
  List* listA = newList(0);
  int i;
  for (int i = 1; i <= 10; i++) {
    listA = cons(i, listA);
  }
  printf("FirstCase: loop? %c\n", loop_existence(listA)?'T':'F'); // should be F
  List* lastIdx = nth_cdr(listA, 10);
  // Check for Safety
  if (!lastIdx) {
    printf("Something is going wrong...");
    destroy(listA);
    return 0;
  }
  lastIdx->cdr = nth_cdr(listA, 2); // loop last index -> second index
  printf("SecondCase: loop? %c\n", loop_existence(listA)?'T':'F'); // should be T
  lastIdx->cdr = NULL;
  destroy(listA);
  return 0;
}