Programming Geek
Rated 4.1/5 based on 446 reviews

Reversing a Linked List

Reversing a linked list means changing the order of the node i. e. the first node becomes the last node and the last node becomes the first node.  A linked list can be reversed using three variable called pre(previous node pointer), cur (current node pointer) and next(next node pointer) and performing following operations while next is not null:
               
          1) make cur link part to point to pre.
          2)make pre to point to pre.
          3) make next to point to next node.
          4)assign next to cur as this will be current node in next iteration.

This is illustrated in following C program:



//reversing  a linked list
/**
*
*@author VIKASH VIK VIKASHVVERMA
*
*/

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

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

void add(node**s,int num)
{
 node*temp=(node*)malloc(sizeof(node));
 temp->data=num;
 temp->next=*s;
 *s=temp;
}

void traverse(node*s)
{
 while(s!=NULL)
 {
  printf("%d\t",s->data);
  s=s->next;
 }
}
void reverse(node**s)
{
 node*pre=NULL,*cur=NULL,*next=NULL;
 cur=*s;
 next=*s;
 while(next!=NULL)
 {
 
 next=cur->next;
 cur->next=pre;
 pre=cur;
 cur=next;
 
 }
 *s=pre;
}


void main()
{
 node*n=NULL;
 
 add(&n,5);
 add(&n,7);
 add(&n,18);
 add(&n,12);
 add(&n,78);
 add(&n,-13);
 traverse(n);
 reverse(&n);
 traverse(n);
}