How to Reverse the Linked List in C++
This article will demonstrate how to reverse a linked list data structure in C++.
Use Iterative Function to Reverse the Linked List in C++
We assume that the target object is a singly linked list and implement code snippets accordingly. At first, we need to look at the basic function utilities in the driver code implemented to demonstrate the example.
The linked list node is a simple struct with a single string data object and a pointer to the next node. We also have the addNewNode function that takes two arguments, Node* and a reference to the string. The addNewNode function is invoked multiple times in the main routine to construct a new list object and store strings from the data_set vector. The function allocates each node on dynamic memory and returns the pointer to the newly created node.
Another useful function for our linked list data structure is printNodes, which is used to output data from every node to the cout stream. The latter one will help us loosely verify the correctness of the reversal function. Note that printNodes keeps the count of nodes during the list traversal and prints the index for each element. Finally, we need to deallocate all nodes before the program exits. This step is not necessary for reversal function demonstration, but it’s important for any real-world project to clean up all the memory allocated during run-time.
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct Node {
struct Node *next{};
string data;
};
struct Node *addNewNode(struct Node *node, string &data) {
auto new_node = new Node;
if (node) node->next = new_node;
new_node->next = nullptr;
new_node->data = data;
return new_node;
}
void freeNodes(struct Node *node) {
struct Node *tmp = nullptr;
while (node) {
tmp = node;
node = node->next;
delete tmp;
}
}
void printNodes(struct Node *node) {
auto count = 0;
while (node) {
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
int main() {
struct Node *tmp, *head = nullptr;
vector<string> data_set = {"Rocket Lake", "Alder Lake", "Tiger Lake",
"Meteor Lake"};
head = addNewNode(head, data_set.at(0));
tmp = head;
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
tmp = addNewNode(tmp, *it);
}
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
Output:
node 0 - data: Rocket Lake
node 1 - data: Alder Lake
node 2 - data: Tiger Lake
node 3 - data: Meteor Lake
Once we initialize a new linked list and store the head of the list in a separate pointer, we can use it to reverse the contents. In this case, we implemented the reverseList function, which accepts a single Node* argument and returns a new root node. At first, we duplicate the passed pointer and store it as a head variable. We also need two additional Node type pointers to do internal book-keeping during the while loop.
The reversal algorithm can be described as follows: We store the next node pointer in a temporary variable (next) and assign the nullptr value to the original one. As a result, the original head node will be pointing to the nullptr as its next node in the list. Next, we update the head variable to store the next (the second) node in the original list and also save the address of the original head node in a separate temporary variable.
We repeat the previous steps until the head pointer evaluates to nullptr, which would mean that the end of the list is reached. In the end, we return the address of the new head node stored in n temporary variable. Consequently, the main program calls the printNodes function for the user to compare modified linked list contents.
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct Node {
struct Node *next{};
string data;
};
struct Node *addNewNode(struct Node *node, string &data) {
auto new_node = new Node;
if (node) node->next = new_node;
new_node->next = nullptr;
new_node->data = data;
return new_node;
}
void freeNodes(struct Node *node) {
struct Node *tmp = nullptr;
while (node) {
tmp = node;
node = node->next;
delete tmp;
}
}
void printNodes(struct Node *node) {
auto count = 0;
while (node) {
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
Node *reverseList(struct Node *node) {
auto head = node;
Node *n = nullptr;
Node *next = nullptr;
while (head) {
next = head->next;
head->next = n;
n = head;
head = next;
}
return n;
}
int main() {
struct Node *tmp, *head = nullptr;
vector<string> data_set = {"Rocket Lake", "Alder Lake", "Tiger Lake",
"Meteor Lake"};
head = addNewNode(head, data_set.at(0));
tmp = head;
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
tmp = addNewNode(tmp, *it);
}
printNodes(head);
cout << " ----------------------------------- " << endl;
printNodes(reverseList(head));
freeNodes(head);
return EXIT_SUCCESS;
}
Output:
node 0 - data: Rocket Lake
node 1 - data: Alder Lake
node 2 - data: Tiger Lake
node 3 - data: Meteor Lake
-----------------------------------
node 0 - data: Meteor Lake
node 1 - data: Tiger Lake
node 2 - data: Alder Lake
node 3 - data: Rocket Lake
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook