A linked list can be reversed by changing the direction of
the pointer, iteratively.
the pointer, iteratively.
Algorithm for reversing the linked list
Let us take three pointer variables P, q and r.
P references the linked list reversed so far, q points to
the linked list to be reversed and r points to the next node of q.
the linked list to be reversed and r points to the next node of q.
Initially, P=NULL; q=head; r=q->next;
while(all nodes have not been reversed )
{
Reverse
the node pointed by q.
the node pointed by q.
q->next=P;
move P,
q, r forward by a node.
q, r forward by a node.
P=q;
q=r;
r=r->next;
}
Also Read: Concatenation of two Linked Lists
C Program to Reverse a Linked List
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node *next;
}node;
node *create(int);
void print(node *);
node *invert(node *);
int main()
{
node *head,*P;
int n;
printf(“Enter how many nodes? “);
scanf(“%d”,&n);
printf(“nEnter nodes: “);
head=create(n); //create function returns the address of first node
printf(“nOriginal Linked List: “);
print(head);
P=invert(head);
printf(“nnReversed Linked List: “);
print(P);
return 0;
}
node* create(int n)
{
node *head,*P;
int i;
head=(node*)malloc(sizeof(node));
head->next=NULL;
scanf(“%d”,&(head->data));
P=head;
//create subsequent nodes
for(i=1;i<n;i++)
{
P->next=(node*)malloc(sizeof(node));
//new node is inserted as the next node after P
P=P->next;
scanf(“%d”,&(P->data));
P->next=NULL;
}
return(head);
}
void print(node *P)
{
while(P!=NULL)
{
printf(“<- %d ->”,P->data);
P=P->next;
}
}
node *invert(node *head) //reverse a linked list pointed by head
{
node *P,*q,*r;
//initial values of P, q and r
P=NULL;
q=head;
r=q->next;
//until all nodes have reversed
while(q!=NULL)
{
q->next=P;
P=q;
q=r;
if(r!=NULL)
r=r->next;
}
return(P);
}
