Linked lists are fundamental data structures used in programming to store and manipulate data. They consist of nodes that hold data and pointers to the next node, forming a chain-like structure. Reversing a linked list involves changing the order of the nodes, with the last node becoming the first and vice versa.
In this tutorial, we will be solving the problem of reversing a Linked List by completely reversing the order of the data nodes in it. In simpler words, the data node at the end should become the starting point of the Linked List.
How can we do that?
Reversing of a linked list means that the head pointer will point to the terminal node of the linked list or the last node of the linked list and the existing head will be pointing towards NULL.
This can be easily done with the help of three pointers where with each traversal through the linked list they keep on reversing the pointer to the next node in the linked list.
Algorithm:
Define a function to reverse the linked list with arguments as the reference to the head node and follow the steps below to get the desired output:
Step 1: Define three nodes one with the reference to the head node, and the other two nodes as NULL.
Step 2: Now run a loop that will be used to traverse the linked list once until the next node does not become NULL.
Step 3: Now inside the loop, the first NULL node is defined as the next node to the head node.
Step 4: Secondly, the next node of the head node is defined as the second NULL node.
Step 5: Now, the second NULL node in Step 4 is again redefined as the node which holds the reference to the head node in Step 1.
Step 6: And finally, the node holding the reference to the head node in Step 1 is made to hold the reference to the next node in the linked list, and hence, the pointer now points to its previous node.
Implementation of the Algorithm:
#include<bits/stdc++.h>
using namespace std;
struct node {
int data;
struct node *next;
};
/* Function to push nodes in a linked list. */
void push(struct node **head_ref, int data) {
struct node *node;
node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->next = (*head_ref);
(*head_ref) = node;
}
/* Function to reverse the nodes in a linked list. */
void reverse(struct node **head_ref) {
struct node *temp = NULL;
struct node *prev = NULL;
struct node *current = (*head_ref);
while(current != NULL) {
temp = current->next;
current->next = prev;
prev = current;
current = temp;
}
(*head_ref) = prev;
}
/* Function to print the nodes in a linked list. */
void printnodes(struct node *head) {
while(head != NULL) {
cout<<head->data<<" ";
head = head->next;
}
}
/* Driver function to check the above algorithm. */
int main() {
struct node *head = NULL;
push(&head, 10);
push(&head, 11);
push(&head, 18);
push(&head, 60);
push(&head, 94);
push(&head, 100);
cout << "List before reversing" << endl;
printnodes(head);
reverse(&head);
cout << endl;
cout << "List after reversing"<<endl;
printnodes(head);
return 0;
}
For the above program, the time complexity is: O(n)
The output of the above algorithm:
List before reversing
100 94 60 18 11 10
List after reversing
10 11 18 60 94 100
Now let's try to understand what we actually did in the above program using the pictorial representation below.
Explanation of the Algorithm to Reverse the Linked List :
Let us take an example of the linked list as shown in the below diagram:
Now let's follow the following steps to reverse the given linked list:
-
Let the first node be the current node which holds the reference to the head node as shown in the diagram below.
-
Now, we will traverse the whole linked list till the next head node does not become NULL. To do so, we will set the next node of the head node as a temp, as shown in the diagram below.
-
Now, the temp node stores the reference to the next node of the head node as shown in the diagram above. Then, we will make the next node of a current link to the previous(in this case NULL), to understand this see the arrow getting created to the Null node on the left of the Node with data 100.
-
We will then set the prev pointer to the new NULL node created which is also the previous of the current node and then move the current node one node ahead and the loop will start again with the temp pointer getting moved to the next of the current pointer.
We will also make the next of the current point to the previous which will change the direction of the arrow, then move the current to next and the previous to next too.
-
-
-
-
-
-
-
-
-
-
-
-
And, finally, the terminal node becomes the head node and the output is shown in the diagram above.
Conclusion
Reversing a linked list is a common task in programming, and understanding how to implement it in C++ is essential for efficient data manipulation. Whether you choose an iterative or recursive approach, reversing a linked list requires updating the pointers of each node to change the order.
By following the guidelines outlined in this article and exploring the frequently asked questions, you will gain the necessary knowledge to tackle this operation with confidence. Mastering the art of reversing linked lists will enhance your programming skills and open up new possibilities for data processing and algorithm design.
Frequently Asked Questions(FAQs)
1. What is a linked list?
A linked list is a data structure that consists of a sequence of nodes, where each node contains data and a pointer to the next node in the list.
2. Why would I need to reverse a linked list?
Reversing a linked list can be useful in various scenarios, such as displaying data in reverse order, implementing algorithms that require reverse traversal, or efficiently manipulating data in certain applications.
3. How do I reverse a linked list in C++?
To reverse a linked list in C++, you can use an iterative or recursive approach. Both methods involve updating the pointers of each node to reverse the order.
4. What is an iterative approach to reversing a linked list?
In an iterative approach, you maintain three pointers: one for the current node, one for the previous node, and one for the next node. By adjusting the pointers, you can reverse the list by traversing it only once.
5. How can I reverse a linked list recursively in C++?
To reverse a linked list recursively, you can define a recursive function that reverses the list starting from a given node. The function will reverse the remaining part of the list and then update the pointers accordingly.
You may also like:
