Interview question – Linked list June 1, 2011

/*
Given a linked list of the form, 1->2->3->4->5->6, convert it into the form 2->1->4->3->6->5. Note that the nodes need to be altered and not the data contained in them; 

*/

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


struct node{
 int a;
 struct node *next;
}*start=NULL;



void add(int item)
{
  struct node *tmp=(struct node *)malloc(sizeof(struct node));
  struct node *tmp2;
  tmp->a=item;
  tmp->next=NULL;

  tmp2=start;
  if(tmp2!=NULL)
  {
  while(tmp2->next!=NULL) tmp2=tmp2->next;
  
    tmp2->next=tmp;
  }
  else
   start=tmp;
  

}

void display()
{
  struct node *tmp=start;
  while(tmp!=NULL){
    printf("%d ",tmp->a);
    tmp=tmp->next;
  }
}

void reverse()
{
  struct node *tmp=start;
  struct node *tmp2=start->next;
  struct node *tmp3=tmp2;
  if(start->next==NULL) return;
  tmp->next=NULL;
  while(tmp2!=NULL)
  {
    tmp3=tmp2->next;
    tmp2->next=tmp;
    tmp=tmp2;
    tmp2=tmp3;
  }
   start=tmp;
   
}



void swap()
{
   struct node *tmp=start;
   struct node *tmp2=tmp->next,*tmp3,*save;
   if(tmp2==NULL) return;
   
   if(tmp2->next==NULL) 
   {
      tmp3=tmp;
      tmp->next=tmp2->next;
      tmp2->next=tmp;
      start=tmp2;
      return ;
   }

   if(tmp2->next->next==NULL)
   {
      tmp3=tmp2->next;
      tmp->next=tmp3;
      tmp2->next=tmp;
      start=tmp2;
      return ;
    }       
   
   
   tmp3=tmp2->next;
   tmp2->next=tmp;
   tmp->next=tmp3->next;
   start=tmp2;
   tmp=tmp3;
   tmp2=tmp->next;
   while(1)
   {
     if(tmp2==NULL||tmp2->next==NULL||tmp2->next->next==NULL) break;     
     tmp3=tmp2->next;
     if(tmp==NULL||tmp3->next==NULL) break;
     tmp2->next=tmp;
     tmp->next=tmp3->next;
   
     
     tmp=tmp3;
     
     tmp2=tmp->next;
     
    
          
   }
   
   if(tmp!=NULL&&tmp2!=NULL)
   {
     if(tmp2->next==NULL)
     {
      tmp2->next=tmp;
      tmp->next=NULL;
      
     }
     else if(tmp2!=NULL)
     {
       
       save=tmp2->next;
       tmp2->next=tmp;
       tmp->next=save;
       
     }
   }
   
}   
     
     
   
   


int main()
{
  int item;
  printf("enter the item one by one\nenter -1 to stop\n");
  while(1)
  {
     
     item;
     
     scanf("%d",&item);
     if(item==-1) break;
     add(item);
  }
  printf("\nThe single linked list is\n");
  display();
  reverse();
  printf("\nThe reversed linked list is\n");
  display();
  printf("\nThe single linked list is\n");
  reverse();
  display();
  printf("\nThe swapped(only 2 adjacent elements) linked list is\n");
  printf("\nGiven a linked list of the form, 1->2->3->4->5->6, convert it into the form 2->1->4->3->6->5. Note that the nodes need to be altered and not the data contained in them.\n\n"); 
  swap();
  display();

return 0;
}