#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define TRAILER -9999

struct Node {
  int data;
  struct Node *next;
};

struct Node *head = NULL;

void Display(struct Node *p) {
  if(p == NULL) return;
  printf("%d ", p->data);
  Display(p->next);
}

void append(int x) {
  struct Node *temp = (struct Node*) malloc (sizeof(struct Node));
  struct Node *temp1 = (struct Node*) malloc (sizeof(struct Node));
  temp->data = x;
  temp->next = NULL;
  if(head == NULL) head = temp;
  else {
    temp1 = head;
    while(temp1->next != NULL) {
      temp1 = temp1->next;
    }
    temp1->next = temp;
  }
  printf("List: ");
  Display(head);
  printf("\n");
}

void countNodes() {
  int counter = 0;
  struct Node *temp = (struct Node *) malloc (sizeof(struct Node));
  temp = head;
  while(temp != NULL) {
    temp = temp->next;
    counter++;
  }
  printf("Nodes = %d\n", counter);
}

void searchList() {
  int x;
  printf("Enter the value to be searched: ");
  scanf("%d", &x);
  struct Node *temp = (struct Node *) malloc (sizeof(struct Node));
  temp = head;
  int counter = 0;
  while(temp->next != NULL) {
    counter++;
    if(temp->data == x) {
      printf("%d is stored in node #%d\n", x, counter);
      break;
    }
    temp = temp->next;
  }
  if(temp->next == NULL && temp->data != x) {
    printf("%d is not present in the list\n", x);
  }
}

void reverseList(struct Node *p) {
  if(p->next == NULL) {
    head = p;
    return;
  }
  reverseList(p->next);
  struct Node *q = p->next;
  q->next = p;
  p->next = NULL;
}

void menu() {
  int input;
  do {
    printf("\nEnter your preference: \n");
    printf("1 - Count the number of nodes\n");
    printf("2 - Reverse the list\n");
    printf("3 - Search an element in the list\n");
    printf("4 - Exit\n");
    scanf("%d", &input);

    switch(input) {
      case 1: countNodes(); break;
      case 2:
        reverseList(head);
        printf("Reversed List: ");
        Display(head);
        printf("\n");
        break;
      case 3: searchList(); break;
      case 4: break;
      default: printf("Invalid input\n"); break;
    }
  } while(input != 4);
}

int main() {
  int input, x;
  while(x != TRAILER) {
    printf("Enter value (%d to exit): ", TRAILER);
    scanf("%d", &x);
    if(x != TRAILER) append(x);
  }

  menu();

  return 0;
}