C++ program to reverse a linked list by changing links between nodes

Reversing a linked list by changing links between nodes in C++

How to reverse a in Singly Linked List in C++?

Reversing a linked list means to swap the position of first and last node, second and second last node and so on. In this article we will learn how to code a C++ program to reverse a linked list by changing links between nodes. If a linked list is reversed by changing its link between nodes then its head node will become tail node and its tail node will become head node. As the linked list is reversed its previous tail node i.e. the last node will no more point to NULL . Now previous head node that is the first node will point to NULL.

Further in this article we will learn steps and algorithm to do the same.

Steps to write a C++ program to reverse a linked list by changing links between nodes

These steps are used to reverse the linked list in CPP programming

  1. Start the program and initialize the variables.
  2. Create function to create list (listBanao).
  3. The above created function will help us to create linked list.
  4. Now create another function to reverse linked list (reverse).
  5. This function will have our main algorithm to reverse the given linked list.
  6. Now create a function to display the linked list(listDhikhao).
  7. This function will help to display the linked list whenever we want to display it.
  8. In the main method we can use these created function as per our need.

As we have followed the above steps our linked list is reversed.

How to struct node of a linked list?

Syntax

class Node  

    int data; 
    Node *next; 
}; 
Algorithm for C++ program for reversing a linked list by changing the links between the nodes in C++

Algorithm to reverse a linked list by changing links between nodes

Below is the algorithm used to reverse linked list in C++

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

Program to reverse singly linked list in C++

#include <iostream>
using namespace std;

struct node 
{
    int num;                
    node *nextptr;             
}*stnode; //node constructed

void listBanao(int n);                 
void reverse(node **stnode);	            
void listDhikhao();
 
int main()
{
    int n,num,item;
		
    cout<<"Enter the number of nodes: ";
    cin>>n;
    listBanao(n);
    cout<<"\nLinked list data: \n";		
    listDhikhao();
    cout<<"\nAfter reversing\n";
    reverse(&stnode);
    listDhikhao();
   return 0;
}
void listBanao(int n) //function to create linked list.
{
    struct node *frntNode, *tmp;
    int num, i;
 
    stnode = (struct node *)malloc(sizeof(struct node));
    if(stnode == NULL)        
    {
        cout<<" Memory can not be allocated";
    }
    else
    {
                                  
        cout<<"Enter the data for node 1: ";
        cin>>num;
        stnode-> num = num;      
        stnode-> nextptr = NULL; //Links the address field to NULL
        tmp = stnode;
 
        for(i=2; i<=n; i++)
        {
            frntNode = (struct node *)malloc(sizeof(struct node)); 
 

            if(frntNode == NULL) //If frntnode is null no memory cannot be allotted
            {
                cout<<"Memory can not be allocated";
                break;
            }
            else
            {
                cout<<"Enter the data for node "<<i<<": "; // Entering data in nodes.
                cin>>num;
                frntNode->num = num;         
                frntNode->nextptr = NULL;    
                tmp->nextptr = frntNode;     
                tmp = tmp->nextptr;
            }
        }
    }
} 

void reverse(node **stnode) //function to reverse linked list
{
    struct node *temp = NULL;
    struct node *prev = NULL;
    struct node *current = (*stnode);
    while(current != NULL) {
        temp = current->nextptr;
        current->nextptr = prev;
        prev = current;
        current = temp;
    }
    (*stnode) = prev;
}
void listDhikhao()//function to display linked list
{
    struct node *tmp;
    if(stnode == NULL)
    {
        cout<<"List is empty";
    }
    else
    {
        tmp = stnode;
        while(tmp != NULL)
        {
            cout<<tmp->num<<"\t";   
            tmp = tmp->nextptr;                 
        }
    }
}
Output:
Enter the number of nodes: 4
Enter the data for node 1: 11
Enter the data for node 2: 32
Enter the data for node 3: 25
Enter the data for node 4: 69

Linked list data: 
11	32	25	69	
After reversing:
69	25	32	11

Want to learn more Data Structure?