Home > Article > Backend Development > Reverse a linked list using C++
In this article, we need to reverse the link with the help of a singly linked list. Our task is to create a function that can reverse a given singly linked list. For example
Input: Following Linked list : 1->2->3->4->NULL Output: After processing of our function: 4->3->2->1->NULL
There are different ways to reverse a linked list. Usually, we think of a simple way of reversing the linked list while traversing it.
In this method, we will traverse the linked list and try to reverse it during the traversal.
#include<bits/stdc++.h> 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; } // Function to print linked list void reverse() { auto curr = head; // current pointer Node* prev = NULL; // previous pointer while(curr) { auto temp = curr -> next; curr -> next = prev; prev = curr; head = prev; curr = temp; } } 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 list; list.push(20); list.push(4); list.push(15); list.push(85); list.print(); list.reverse(); cout << "\n"; list.print(); }
85 15 4 20 20 4 15 85
In this approach, we just iterate through the list and reverse it during the iteration. This is a good approach because the time complexity is O(N), where N is the size of our list.
Now we try to do an experiment and try to reverse the list using the stack.
We will use a stack to store all the nodes in this program and reverse them by traversing the stack.
#include<bits/stdc++.h> 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; } // Function to print linked list void reverse() { auto curr = head; // current pointer Node* prev = NULL; // previous pointer stack<Node *> s; while(curr) { s.push(curr); curr = curr -> next; } prev = s.top(); head = prev; s.pop(); while(!s.empty()) { auto temp = s.top(); s.pop(); prev -> next = temp; prev = temp; } prev -> next = NULL; } 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 list; list.push(20); list.push(4); list.push(15); list.push(85); list.print(); list.reverse(); cout << "\n"; list.print(); }
85 15 4 20 20 4 15 85
In this method we store the list nodes in the stack while traversing the list , then use the stack to pop them and reverse the list; the time complexity of this approach is also O(N), where N is our list size. As before, we used the stack, so we can also use the recursive method, because recursion also uses the stack, and now we will use the recursive method.
In this method we will perform the same process as before but using recursive calls.
#include<bits/stdc++.h> 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; } // Function to print linked list void rreverse(Node *curr, Node *prev) { if(curr == NULL) { // prev -> next = curr; head = prev; return; } rreverse(curr -> next, curr); curr -> next = prev; prev -> next = NULL; } void reverse() { auto curr = head; // current pointer Node* prev = NULL; // previous pointer rreverse(curr -> next, curr); } 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 list; list.push(20); list.push(4); list.push(15); list.push(85); list.print(); list.reverse(); cout << "\n"; list.print(); }
85 15 4 20 20 4 15 85
In this method we are doing the same as before but using recursive calls so the time complexity of this method is also O(N), where N is the size of our list.
In this article, we solved the problem of inverting a singly linked list. We also learned the C program and the complete method (normal method and two other methods) to solve this problem. We can write the same program in other languages like C, Java, Python and others. Hope you find this article helpful.
The above is the detailed content of Reverse a linked list using C++. For more information, please follow other related articles on the PHP Chinese website!