C Program to Reverse a Linked List

A linked list can be reversed by changing the direction of
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.
Initially, P=NULL; q=head; r=q->next;
while(all nodes have not been reversed )
{
                Reverse
the node pointed by q.
                q->next=P;
                move P,
q, r forward by a node.
                P=q;
                q=r;
                r=r->next;
}

Reverse a Linked List

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);
}

C Program to Reverse a Linked List
Category: DSA

Leave a Reply

Your email address will not be published. Required fields are marked *