Many of you must be familiar with the application of a linked list in the real world and its importance. We use linked lists to maintain a directory of names, dynamic allocation of memory, and create an implementation of essentials data structures like stacks and queues, and what not?
Knowing all this in this tutorial we are going to discuss the basic understanding of a linked list, and implement and analyze how to reverse a linked list in C++. Let’s get Kraken!
What is Linked List?
The general definition is that a linked list is a sequence of data structures, the nodes are connected with pointers, and the last node points to NULL.
A linked list is a sequence of links that contain elements connected using pointers. Each link which is a pointer contains a connection to another node. The linked list is the second most utilized data structure after arrays.
There are three components of a linked list:
Node − Each node stores data which is called an element.
Next − Every node of a linked list contains a link to the next link that is Next.
Head − A Linked List contains the pointer to the first link called a head pointer.
How to Reverse a Linked List?
Reversing the list implies reversing all the elements and we can do it by reversing all the links and make the next pointer point to the previous node.
Problem Description
In this problem statement we are provided with the pointer or reference to the head of a singly linked list, invert the list, and return the pointer or reference to the head of the new reversed linked list.
For example, consider the following linked list:
After reversing the complete linked list we return the pointer to the new linked list as demonstrated in the figure:
There can be two approaches to solve this problem, the following are the hints, try solving the problem by yourself and then head over to the next section to find the solution and C++ code.
Hints
- Think of an iterative approach to find the reversed list in a single pass.
- Or, think of a recursive approach to find the reversed list in a single pass.
Now that you have tried solving the problem yourself given the two types of approaches to solving this problem, let’s discuss both the approaches one by one:
Iterative Solution for Reversing a Linked List
If the linked list has only one or no element, then we return the current list as it is. And if there are two or more elements, then we can implement an iterative solution using three-pointers
We will create a function to reverse the linked list taking reference to the head node and as the only argument and return the head of the new linked list:
Step 1: Define three nodes one with the reference to the head node and name it current, and name the other two nodes temp and prev pointers as NULL.
Step 2: Using a while loop we will traverse the linked list once until the next pointer does not become NULL.
Step 3: While iterating, we perform the following operations:
temp = current->next;
current->next = prev;
prev = current;
current = temp;
We assign the temp node to the next of the current node and then reverse the link by assign the current->next to the previous node. And then increment the previous node to the current node and then the current node to the temp node.
And then we finally return the head node.
Iterative Implementation
The iterative implementation of reversing a linked list in c++ follows:-
#include<bits/stdc++.h> using namespace std; struct node { int data; struct node *next; }; // To create a demo we have to construct a linked list and this // function is to push the elements to the 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 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; } // To check our program void printnodes(struct node *head) { while(head != NULL) { cout<<head->data<<" "; head = head->next; } } // Driver function int main() { struct node *head = NULL; push(&head, 0); push(&head, 1); push(&head, 8); push(&head, 0); push(&head, 4); push(&head, 10); cout << "Linked List Before Reversing" << endl; printnodes(head); reverse(&head); cout << endl; cout << "Linked List After Reversing"<<endl; printnodes(head); return 0; }
Output:
Linked List Before Reversing
10 4 0 8 1 0
Linked List After Reversing
0 1 8 0 4 10
Time complexity:
O(N) because we iterate through each element at least once.
Space complexity:
O(1) because no extra space was used here.
Recursive solution for Reversing a Linked List
The most important thing to remember in this approach is that the recursive approach uses a stack. The compiler allocates stack memory after each recursive call, and this solution can run out of memory in case of very huge linked lists (think billions of elements).
We recursively iterate to each node in the list until we reach the last node and return the new head. We have to note that the last node in this approach will become the new head of the list. On the return path, each node is going to append itself to the end of the partially reversed linked list.
Recursive Implementation
The recursive implementation of reversing a linked list in c++ follows:-
#include using namespace std; struct Node { int data; struct Node* next; Node(int data) { this->data = data; next = NULL; } }; struct LinkedList { Node* head; LinkedList() { head = NULL; } Node* reverse(Node* head) { if (head == NULL || head->next == NULL) return head; // Recursive call Node* rest = reverse(head->next); head->next->next = head; head->next = NULL; return rest; } void print() { struct Node* temp = head; while (temp != NULL) { cout << temp->data << " "; temp = temp->next; } } void push(int data) { Node* temp = new Node(data); temp->next = head; head = temp; } }; int main() { LinkedList ll; ll.push(320); ll.push(34); ll.push(315); ll.push(385); cout << "Linked List Before Reversing\n"; ll.print(); ll.head = ll.reverse(ll.head); cout << "\nLinked List After Reversing \n"; ll.print(); return 0; }
Output:
Linked List Before Reversing
385 315 34 320
Linked List After Reversing
320 34 315 385
Time Complexity:
O(N) because we iterate through each element at least once.
Space complexity:
O(N) because we create a recursive stack each time we call the reverse function recursively.
Conclusion
In this tutorial, we learned how to reverse a link using two approaches, and discussed the code in C++. This question is frequently asked in technical interviews by huge companies like Amazon and Google.
