Reversing a linked list in C++:
Reversing a linked list in C++ or any other programming languages works in a same way. We needs to follow few steps for that. In this post, I will show you how to reverse a linked list in C++ with example.
Steps to reverse a linked list:
We need three variables to do the reverse operation. One to hold the previous node, one to hold the current node and another one to hold the next node temporarily. At the beginning, current node will have the same value as head and previous node and temp node will be NULL.
- tempNode is the node at front, currentNode is the middle node and prevNode is the last node.
- Assign next of currentNode to tempNode
- Assign prevNode to next of currentNode
- Assign currentNode to prevNode
- Assign tempNode to currentNode
On each step, we are pointing the current node to its previous node and tempNode to the next of current node. This loop will run until the value of currentNode is NULL.
prevNode will point to the last node of the linked list once the loop will complete.
If we write it in code, it looks as like below :
void reverse()
{
Node *tempNode = NULL;
Node *prevNode = NULL;
Node *currentNode = head;
while (currentNode != NULL)
{
tempNode = currentNode->next;
currentNode->next = prevNode;
prevNode = currentNode;
currentNode = tempNode;
}
head = prevNode;
}At the end, we assigning the value of prevNode to head.
Complete C++ program:
Below is the complete C++ program that allows you to add a node, reverse a linked list and view the content of the linked list.
#include <iostream>
using namespace std;
struct Node
{
int value;
Node *next;
};
class LinkedList
{
Node *head = NULL;
public:
void insertAtHead(int value)
{
Node *node = new Node;
node->value = value;
if (head == NULL)
{
node->next = NULL;
}
else
{
node->next = head;
}
head = node;
}
void displayList()
{
Node *flag = head;
while (flag != NULL)
{
cout << "->" << flag->value;
flag = flag->next;
}
cout << endl;
}
void reverse()
{
Node *tempNode = NULL;
Node *prevNode = NULL;
Node *currentNode = head;
while (currentNode != NULL)
{
tempNode = currentNode->next;
currentNode->next = prevNode;
prevNode = currentNode;
currentNode = tempNode;
}
head = prevNode;
}
};
int main()
{
int choice, value;
LinkedList linkedList;
while (1)
{
int exit = 0;
cout << "Enter 1 to insert, 2 to display, 3 to reverse and -1 to exit :" << endl;
cin >> choice;
switch (choice)
{
case -1:
exit = 1;
break;
case 1:
cout << "Enter a value :" << endl;
cin >> value;
linkedList.insertAtHead(value);
break;
case 2:
linkedList.displayList();
break;
case 3:
linkedList.reverse();
break;
}
if (exit == 1)
{
break;
}
}
return 0;
}This is a complete example that can insert a node, display all nodes and reverse a linked list based on user input.
Sample Output :
Enter 1 to insert, 2 to display, 3 to reverse and -1 to exit :
1
Enter a value :
10
Enter 1 to insert, 2 to display, 3 to reverse and -1 to exit :
1
Enter a value :
11
Enter 1 to insert, 2 to display, 3 to reverse and -1 to exit :
1
Enter a value :
12
Enter 1 to insert, 2 to display, 3 to reverse and -1 to exit :
2
->12->11->10
Enter 1 to insert, 2 to display, 3 to reverse and -1 to exit :
3
Enter 1 to insert, 2 to display, 3 to reverse and -1 to exit :
2
->10->11->12In this example, we have inserted three values to the linked list and reversed them.
