C Program for Reversing a linked list by changing links between the nodes

reverse a linked list by changing links between the nodes in C Programming Language

Reverse a Linked List by changing the links between the nodes

Here we will learn how to code a C program for reversing a linked list by changing the links between the nodes. That is, in this program we will be reversing the pointers of the node. i.e, if the user entered 1,2,3,4,5 in the linked list, the linked list will be reversed and the output will be 5,4,3,2,1. Let’s see how to code a C program for this problem

How to reverse a Linked List by changing the links between the nodes

  • Step 1 – We will take three pointers ptr1, ptr2 and ptr3. Initially the first and the third pointer will point NULL, and  the second pointer will point the head.
  • Step  2 – We will iterate through the linked list, swapping the value of these 3 pointers.
  • Step 3 – ptr3 will now point the second node of the linked, and ptr2 will be removed from the linked list.
  • Step 4 – Now ptr1 will point the removed node.
  • Step 5 – ptr2 node will point ptr1 node.
  • Step 6 – All the three pointers will be moved by +1.
  • Step 7 – The above steps will be repeated until ptr3 points the NULL.
  • Step 8 – Than in the last step, the last node will become the HEAD of the linked list
C Program for Reversing a Linked List by changing Links between the nodes

Algorithm for reversing the data of a linked list

  • START WHILE
  • NEXT=CURRENT->NEXTPTR
  • CURRENT->NEXTPTR=PREV
  • PREV=CURRENT
  • CURRENT=NEXT
  • END WHEN CURRENT=NULL
  • HEAD_ADDR=PREV

 

C Program for Reversing a Linked List, by changing links between the nodes

#include <stdio.h> 
#include <stdlib.h> 
  
/* Link list node */
struct Node { 
    int data; 
    struct Node* next; 
}; 
//declaring the prototype of the methods that we will be using
void reverseLinkedList(struct Node** head_addr) ; 
void insert(struct Node** head_ref, int new_data) ;
void displayLinkedList(struct Node* head) ;

int main() 
{ 
    int i,n,data;
    /* Start with the empty list */
    struct Node* head = NULL; 
    printf("Enter the number of nodes");
    scanf("%d",&n);
    printf("Enter the data in the nodes");
    for(i=0;i<n;i++)
    {
        scanf("%d",&data);
        insert(&head, data); 

        
    }
  
    printf("Given linked list\n"); 
   reverseLinkedList(&head); 
    displayLinkedList(head); 

    printf("\nReversed Linked list \n"); 
    reverseLinkedList(&head); 
    displayLinkedList(head); 
    getchar(); 
}
/* Function to reverse the linked list */
 void reverseLinkedList(struct Node** head_addr) 
{ 
    struct Node* prev = NULL; 
    struct Node* current = *head_addr; 
    struct Node* next = NULL; 
    while (current != NULL) { 
        // Store next 
        next = current->next; 
  
        // Reverse current node's pointer 
        current->next = prev; 
  
        // Move pointers one position ahead. 
        prev = current; 
        current = next; 
    } 
    *head_addr = prev; 
} 
  
/* Function to push a node */
void insert(struct Node** head_addr, int new_data) 
{ 
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); 
    new_node->data = new_data; 
    new_node->next = (*head_addr); 
    (*head_addr) = new_node; 
} 
  
/* Function to print linked list */
void displayLinkedList(struct Node* head) 
{ 
    struct Node* temp = head; 
    while (temp != NULL) { 
        printf("%d  ", temp->data); 
        temp = temp->next; 
    } 
} 
Quiz time

Fun Fact

Problems for performing different operations on Linked List are asked in various coding competitions, either directly or in the form of a logical problem. Here we have described one of the manner of reversing a Linked list, but there are few more ways of reversing a linked list according to your needs, like Reversing it without changing the links, or just reverse printing the data.