C++

Reversed Linked List (C++)

When you reverse a linked list, the link path is reversed, and the head becomes the tail, and the tail becomes the head. By swapping the positions of the nodes, we can understand this quickly. In this swapping, we just change the positions of the nodes from left to right or vice-versa.

linked list: This is a linked list that we want to reverse.

After reversed linked list: The below will be the result after reversing the above-linked list.

In the above example diagram, we can see that the head node and the tail node change their positions when we reverse the linked list. The head node, which is now a tail node, points to the null node because it is now a tail node.

Algorithm Steps

  1. We create a main method and declare some required variables.
  2. Then, our next step is to create a method that can create a linked list. This method helps us to create a linked list.
  3. The next step is to create a method to reverse the linked list. In this method, we pass the whole linked list, and this method will reverse the linked list.
  4. Now, we need another method to display our result after reversing it.
  5. We will combine all these above methods into our main method.

We are going to explain reversed linked list using some pictorial form to make it easier to understand. So let’s start with the example.

The below is a linked list that we want to reverse.

Step 1. The green-colored node is a head node, which points to the first node in the startup.

Step 2. In the next step, we will traverse the whole linked list until we do not get the null pointer next to the header node. For that, we are going to assign the next node a temporary name, as shown in the below diagram.

Step 3. As we have a new reference node named “temporary,” which can help us traverse the whole linked list till we do not get the null pointer, So we can set the next link of the header node as null, which will not affect the linked list as shown below in the diagram. The null pointer next to the current node is called the previous node.

Step 4. Now, we move the temporary node to the next node and the current node to the previous temporary node. So now we have moved to the next node. We also change the previous node from null to just the previous node of the current node. So now the temporary node will take care of all the traverses till the null pointer so that we can set the link of the current node to the previous node, and now it is pointing to the previous node, as shown in the below diagram.

So we follow the same steps and, at last, we will get a reversed linked list.

Step 5.

Step 6.

Step 7.

Step 8.

Step 9.

Step 10.

Step 11.

Step 12.

Step 13.

Step 14. At this step, our linked list reversed.

C++ Program to reverse a linked list

#include <iostream>
using namespace std;

// Method to create the node
struct node
{
    int value;
    node *nextNodePtr;
}*nodeObject;

void createLinkedList(int n);
void reverseLinkedList(node **nodeObject);
void display();

int main()
{
    int n,value,item;

    cout<<"How many nodes you want to create =>: ";
    cin>>n;
    createLinkedList(n);
    cout<<"\nInformation in the linked list: \n";
    display();
    cout<<"\nLinked list after reversed\n";
    reverseLinkedList(&nodeObject);
    display();
   return 0;
}
// This method will create the linked list
void createLinkedList(int n)
{
    struct node *frontNode, *tempNode;
    int value, i;

    nodeObject = (struct node *)malloc(sizeof(struct node));
    if(nodeObject == NULL)
    {
        cout<<" Not enough to assing memory";
    }
    else
    {

        cout<>value;
        nodeObject-> value = value;
        nodeObject-> nextNodePtr = NULL;
        tempNode = nodeObject;

        for(i=2; i<=n; i++)
        {
            frontNode = (struct node *)malloc(sizeof(struct node));

            // When no any node in the linked list
            if(frontNode == NULL)
            {
                cout<<"Memory can not be allocated";
                break;
            }
            else
            {
                cout<<"Please enter the info of node "<<i<>value;
                frontNode->value = value;
                frontNode->nextNodePtr = NULL;
                tempNode->nextNodePtr = frontNode;
                tempNode = tempNode->nextNodePtr;
            }
        }
    }
}

void reverseLinkedList(node **nodeObject)
{
    struct node *tempNode = NULL;
    struct node *previousNode = NULL;
    struct node *currentNode = (*nodeObject);
    while(currentNode != NULL) {
        tempNode = currentNode->nextNodePtr;
        currentNode->nextNodePtr = previousNode;
        previousNode = currentNode;
        currentNode = tempNode;
    }
    (*nodeObject) = previousNode;
}
void display()
{
    struct node *tempNode;
    if(nodeObject == NULL)
    {
        cout<<"Linkedlist is empty";
    }
    else
    {
        tempNode = nodeObject;
        while(tempNode != NULL)
        {
            cout<value<nextNodePtr;
        }
    }
}

Output

How many nodes do you want to create =>: 6
Please enter the info of node 1 (number only): 101
Please enter the info of node 2: 95
Please enter the info of node 3: 61
Please enter the info of node 4: 19
Please enter the info of node 5: 12
Please enter the info of node 6: 11
Information <strong>in</strong> the linked list:
101     95      61      19      12      11
Linked list after reversed
11      12      19      61      95      101

Conclusion

So, we have studied the reverse linked list. We have seen the revered linked list concepts through a pictorial diagram and then implemented the same concepts through the C++ program. There are some other methods to reverse the linked list, but this is a very common method to reverse a linked list. It is up to you to decide how you want to solve your problems. If you just want to focus on problems or time complexity, too.

About the author

Shekhar Pandey