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
- We create a main method and declare some required variables.
- Then, our next step is to create a method that can create a linked list. This method helps us to create a linked list.
- 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.
- Now, we need another method to display our result after reversing it.
- 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
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<<"Please enter the info of node 1 (number only): ";
cin>>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<<": ";
cin>>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<<tempNode->value<<"\t";
tempNode = tempNode->nextNodePtr;
}
}
cout <<endl;
}
Output
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 in the linked list:
101 95 61 19 12 11
Linked list after reversed
11 12 19 61 95 101
Conclusion
This LinuxHint article has reviewed how to reverse a linked list in C++. There are some other methods to reverse a 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, but generally the reverse linked list function should be a simple loop with pointer swaps.
