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

typedef struct item {
  int data;
  struct item * next;
} Item;

Item * push_back(Item * head, int data)
{
  Item * tail = head;
   
  Item * new = (Item *) malloc(sizeof(Item));   /* construct new item */
  if (!new) {
    printf("ERROR: out of memory!\n");
    return NULL;
  }
  new->data = data;
  new->next = NULL;
  if (tail == NULL)                             /* empty list */
    return new;
  while (tail->next != NULL)                    /* search last item */
    tail = tail->next;
  tail->next = new;                             /* insert new item as last */
  return head;
}

void print(Item * head)
{
  if (!head) return;
  printf("%d", head->data);
  for (head = head->next; head; head = head->next)
    printf(" %d", head->data);
  printf("\n");
}

Item * reverse1(Item * head)
{
  Item * item = head, * next;

  if (!head || !head->next)
    return head;
  next = head->next;
  head->next = NULL;
  while (next) {
    Item * tmp = next->next;
    next->next = item;
    item = next;
    next = tmp;
  }
  return item;
}

Item * reverse2(Item * head)
{
  Item * item, * next;
  
  if (!head || !head->next)
    return head;
  next = head->next;
  item = reverse2(head->next);
  next->next = head;
  head->next = NULL;
  return item;
}

void clean(Item * head)
{
  while (head) {
    Item * tmp = head->next;
    free(head);
    head = tmp;
  }
}

int main()
{
  Item * head = NULL;
  if (!(head = push_back(head, 1))) return -1;
  if (!(head = push_back(head, 2))) return -1;
  if (!(head = push_back(head, 3))) return -1;
  if (!(head = push_back(head, 4))) return -1;
  if (!(head = push_back(head, 5))) return -1;
  print(head);
  head = reverse1(head);
  print(head);
  head = reverse2(head);
  print(head);
  clean(head);
  return 0;
}