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

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

void print_linked_list(struct node *head) {
  struct node *temp = head;
  if (temp == NULL) {
	printf("[X]\n");
	return;
  }
  while (temp!=NULL) {  
	printf("%d -> ", temp->data);
	temp = temp->next;
  }
  printf("[X]\n");  
}

void search_linked_list(struct node* head, int data) {
  struct node* temp;
  int pos = 0;
  temp = head;
  while(temp!=NULL) {
	if(temp->data==data)
	  printf("Found %d at position: %d\n", data, pos);
    temp = temp->next;
	pos ++;
  }
}

struct node* insert_linked_list(struct node* head, int i, int index) {
  // test head == NULL
  // if index > length of linked list, return -1

  struct node* temp, *cur;
  temp = (struct node *) malloc(sizeof(struct node));
  temp->data = i;
  if(index == 0) {
	temp->next = head;
	head = temp;
  } else {
	cur = head;
	while (index--) {
	  cur = cur->next;
	}
	temp->next = cur->next;
	cur->next = temp;
  }
  return head;
}

struct node* delete_linked_list(struct node* head, int i) {
  // test head == NULL
  struct node *temp, *temp2;
  if (head->data == i) {
	return head->next;
  }
  temp = head;
  // if know all values unique
/*   while (temp->next->data!=i) { */
/* 	temp = temp->next; */
/* 	if(temp==NULL) break; // not found */
/*   } */
  // otherwise, go through entire list
  while (temp->next != NULL) {
	if (temp->next->data==i) {
	  temp2 = temp->next;
	  temp->next = temp->next->next;
	  free(temp2);
	}
	temp = temp->next;
  }
  // would this be OK now? what if i is the last
  return head;
}

int find_reverse_k(struct node* head, int k) {
  // if k largr than length of linked list, return error
  // using p2 as the runner pointer
  struct node *p1, *p2;
  p1 = head;
  p2 = p1;
  while (k--) p2 = p2->next;
  while(p2!=NULL) {
	p1 = p1->next;
	p2 = p2->next;
  }
  return p1->data;
}

struct node* reverse_linked_list(struct node* head) {
  // single node linked list
  struct node *p1, *p2, *p3;
  if (head->next==NULL) {
	return head;
  }
  p1 = head;
  p2 = p3 = p1->next;
  while(p2!=NULL) {
	p3 = p2->next;
	p2->next = p1;
	p1 = p2;
	p2 = p3;
  }
  head->next = NULL;
  return p1;
}

// simplified version
struct node* reverse_linked_list2(struct node* head) {
  // single node linked list
  struct node *p1, *p2, *p3;
  p1 = NULL;
  p2 = head;
  while(p2!=NULL) {
	p3 = p2->next;
	p2->next = p1;
	p1 = p2;
	p2 = p3;
  }
  return p1;
}


int main(void)
{
  int num;
  struct node *head = NULL;
  struct node *temp;
  int value;

  /*
   * Task1: Create linked list from user input
   */
  
  for(num=0; num<5; num++){
	printf("enter node data: ");
	scanf("%d", &value);
	temp = (struct node *) malloc(sizeof(struct node));
	temp->data = value;
	temp->next = head;
	head = temp;
  }

  /*
   * Task2: Print linked list 
   */
  print_linked_list(head);
  
  /*
   * Task4: Search element
   */

  printf("Search: \n");
  search_linked_list(head, 2);


  /*
   * Task5: Insert element
   */
  printf("Insert: \n");
  head = insert_linked_list(head, 10, 2);
  print_linked_list(head);

  
  /*
   * Task6: Delete element 
   */
  printf("Delete: \n");
  head = delete_linked_list(head, 10);
  print_linked_list(head);

  /*
   * Task7: Find -kth element
   */
  printf("-3th element: \n");
  printf("%d\n", find_reverse_k(head, 3));

  /*
   * Task8: Reverse linked list
   */
  printf("Reverse linked list: \n");
  head = reverse_linked_list2(head);
  print_linked_list(head);
  
  /*
   * Task3: Free linked list space
   */
  printf("Free linked list: \n");
  temp = head;
  while (head->next!=NULL) {
	temp = head;
	head = head->next;
	free(temp);
	print_linked_list(head);
  }
  free(head);   // free will not change value of head
  head = NULL;  // try remove this line
  print_linked_list(head);  

  return 0;
}