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

struct List {
  int val;
  struct List * tail;
};

struct List * from_int(int x) {
  struct List * ans = 
    (struct List*)malloc(sizeof(struct List));
  ans->val = x;
  ans->tail = NULL;
  return ans;
}

struct List* append1(struct List* lst1, struct List *lst2) {
  if(lst1 == NULL)
    return lst2;
  struct List * ans = append1(lst1->tail, lst2);
  struct List * first = from_int(lst1->val);
  first->tail = ans;
  return first;
}

struct List* append2(struct List*lst1, struct List *lst2) {
  if(lst1 == NULL)
    return lst2;
  if(lst2 == NULL)
    return lst1;
  struct List *result = from_int(lst1->val);
  struct List *prev   = result;
  lst1 = lst1->tail;
  while(lst1 != NULL) {
    struct List * first = from_int(lst1->val);
    prev->tail = first;
    prev = first;
    lst1 = lst1->tail;
  }
  prev->tail = lst2;
  return result;
}

void append3(struct List**lst1p, struct List*lst2) {
  struct List* lst1 = *lst1p;
  if(lst1 == NULL) {
    *lst1p = lst2;
    return;
  }
  while(lst1->tail != NULL)
    lst1 = lst1->tail;
  lst1->tail = lst2;
}

int member(struct List *lst, int x) {
  for(; lst != NULL; lst = lst->tail)
    if(lst->val == x)
      return 1;
  return 0;
}

int length1(struct List *lst) {
  if(lst==NULL)
    return 0;
  return 1 + length1(lst->tail);
}
int length2(struct List *lst) {
  int ans = 0;
  while(lst != NULL)
    ++ans;
  return ans;
}

struct List * from_array(int len, int* p) {
  struct List * ans = NULL;
  int i;
  for(i=len-1; i >= 0; --i) {
    struct List * next = from_int(p[i]);
    next->tail = ans;
    ans = next;
  }
  return ans;
}

void print(struct List * lst) {
  printf("\n[");
  while(lst != NULL) {
    printf(" %d ", lst->val);
    lst = lst->tail;
  }
  printf("]\n");
}

void test() {
  int arr1[5] = { 2, 4, 6, 8, 10};
  int arr2[3] = { 1, 2, 3};
  int arr3[4] = {20, 0, 0, 0};
  struct List * lst1 = from_array(5,arr1);
  struct List * lst2 = from_array(3,arr2);
  struct List * lst3 = from_array(4,arr3);
  print(lst1);
  print(lst2);
  print(lst3);
  print(append1(lst1,lst2)); // space leak!
  print(append2(lst1,lst2)); // space leak!
  print(lst1);
  print(lst2);
  append3(&lst1,lst2);
  print(lst1);
  print(lst2);
  append3(&lst1,lst1); // An awfully bad idea!
  // print(lst1); 
}

int main(int argc, char**argv) {
  test();
  return 0;
}