/*
Title: Implement a singly linked list with following options
  1) Insertion of a node at any location
  2) Deletion of a node from any location
  3) display a list
  4) Display in reverse
  5) Reverse the list without using additional data structure.
*/

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

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

node *getnode()
{
node *p;
p=(node*)malloc(sizeof(node));
p->next=NULL;
return p;
}

node *create()
{
node *head=NULL,*p,*last;
int i,n;
printf("\nEnter no of nodes: ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
p=getnode();
printf("\nEnter [%d] node:",i+1);
scanf("%d",&p->data);
if(head==NULL)
head=last=p;
else
{
last->next=p;
last=p;
}
}
return head;
}

void display(node *head)
{
node *temp=head;

if(head!=NULL)
{
printf("\nSingly Linked List: ");
while(temp->next!=NULL)
{
printf("%d->",temp->data);
temp=temp->next;
}
printf("%d",temp->data);
}
else
printf("\nList is Empty\n");
}


node *ins_first(node *head)
{
node *temp,*p;
printf("\nInsert at Beginning\n");
p=getnode();
printf("\nEnter node to be inserted:" );
scanf("%d",&p->data);
if(head==NULL)
head=p;
else
{
p->next=head;
head=p;
}
return head;
}

node *ins_end(node *head)
{
node *temp,*p;
printf("\nInsert at End\n");
p=getnode();
printf("\nEnter node to be inserted:" );
scanf("%d",&p->data);
if(head==NULL)
head=p;
else
{
temp=head;
while(temp->next!=NULL)
temp=temp->next;
temp->next=p;
}
return head;
}

node *ins_any(node *head)
{
node *temp,*p;
int x;
printf("\nInsert at any position\n");
if(NULL==head)
printf("\nList is Empty");
else
{
printf("\nEnter node after which new node to be inserted: ");
scanf("%d",&x);
temp=head;
while(temp!=NULL && temp->data!=x)
temp=temp->next;

if(temp!=NULL)
{
p=getnode();
printf("\nEnter node to be inserted:" );
scanf("%d",&p->data);
p->next=temp->next;
temp->next=p;
}
else
printf("\nData not found");
}
return head;
}

node *del_first(node *head)
{
node *temp;
temp=head;
head=head->next;
free(temp);
return head;
}

node *del_end(node *head)
{
node *temp,*prev;
if(head->next==NULL)
{
temp=head;
head=head->next;
free(temp);
return head;
}
else
{
temp=head;
while(temp->next!=NULL)
{
prev=temp;
temp=temp->next;
}
prev->next=NULL;
free(temp);
}
return head;
}

node *del_any(node *head)
{
int x;
node *temp,*prev;
printf("\nEnter node to be deleted: ");
scanf("%d",&x);
if(head->data==x)
{
temp=head;
head=head->next;
free(temp);
}
else
{
temp=head;
while(temp!=NULL && temp->data!=x)
{
prev=temp;
temp=temp->next;
}
if(temp!=NULL)
{
prev->next=temp->next;
free(temp);
}
else
printf("\nData not found");
}
return head;
}


void reverse(node *head)
{
if(head!=NULL)
{
reverse(head->next);
printf(" %d",head->data);
}
}

node *revert(node *head)
{
node *p,*q,*r;
p=NULL;
q=head;
r=q->next;
while(q!=NULL)
{
q->next=p;
p=q;
q=r;
if(r!=NULL)
r=r->next;
}
return p;
}

int main()
{
int ch,pos;
node *head=NULL,*p;
while(1)
{
system("clear");
display(head);
printf("\n\n*******MENU************");
printf("\n1.Create\n2.Display\n3.Insert\n4.Delete");
printf("\n5.Reverse\n6.Revert\n7.Exit\nEnter ur choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:
head=create();
break;
case 2:
display(head);
getchar();
break;
case 3:
printf("\nEnter Where to insert(start->1,end->2,any->3)");
scanf("%d",&pos);
if(pos==1)
head=ins_first(head);
else if(pos==2)
head=ins_end(head);
else
head=ins_any(head);
printf("\n\nAfter Insertion: ");
display(head);
getchar();
break;
case 4:
if(head!=NULL)
{
printf("\nEnter from Where to delete(start->1,end->2,any->3)");
scanf("%d",&pos);
if(pos==1)
head=del_first(head);
else if(pos==2)
head=del_end(head);
else
head=del_any(head);
}
printf("\n\nAfter Deletion: ");
display(head);
getchar();
break;
case 5:
printf("\nReversed: ");
reverse(head);
getchar();
break;
case 6:
head=revert(head);
display(head);
getchar();
break;
case 7:
exit(0);
}
getchar();
}
return 0;
}




//END OF PROGRAM