Reversing Linked List is an interesting topic in data structure and algorithms. This article describes several algorithms to implement the reverse-linked list.
Reverse a Linked List:
LinkedList is a data structure that stores data in a linear fashion. It is not a continuous method.
Each element of a LinkedList contains a piece of information and an address to the next element of the LinkedList.
The LinkedList element is commonly known as a node.
To return the LinkedList to its original location, the pointer must be reversed so that the next element points to the previous element.
The inputs and outputs are shown below.
The first node is at the beginning of the LinkedList. No other element has a stored address for this.
The LinkedList queue is the last node. Null store in the next address.
You can also reverse the LinkedList and change the head and tail using:
- Iterative Approach
- Recursive Approach
Iterative Approach to Reverse a Linked List:
Iterative approach to reverse linked lists:
To repeatedly flip a LinkedList, you must save a reference to the previous and next element so that it is not lost when you swap the memory address pointer with the next element in the LinkedList.
The following figure shows how to change the reference to reverse the LinkedList.
Here are the steps you need to take to get your linked list back:
Currently, create the next and previous three instances.
Loop through the following until the current is no longer zero.
- Saves the next node of the current element to the next pointer.
- Preset the following for the current node. This is the MVP line.
- Move the former to the present.
After all, the current is one step ahead of the last element, so you have to fix your head on the last element reached. This was previously available.
Put your head forward. Therefore, there is a new header for LinkedList, which is the last element of the old LinkedList.
For example:
Here code:
#include <iostream>
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; }
void reverse()
{
Node* current = head;
Node *prev = NULL, *next = NULL;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
head = prev;
}
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(20);
ll.push(4);
ll.push(15);
ll.push(85);
cout << "Given linked list\n";
ll.print();
ll.reverse();
cout << "\nReversed Linked list \n";
ll.print();
return 0;
}
Time Complexity: O(n) Space Complexity: O(1)
Reverse a Linked List Recursively:
To recursively reverse the LinkedList, you must divide the LinkedList into two parts, header and retention.
The head first refers to the first element. The rest point to the next element from the beginning.
LinkedList recursively traverses to the penultimate element.
When you get to the last item, set it as the head.
From there, until you get to the beginning of the LinkedList, do the following:
node.next.next = node; node.next = null;
Keep a copy of the primary instance so you don’t lose sight of the original header.
Below is a diagram of the above procedure.
For example:
Here Code:
#include <iostream>
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;
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(20);
ll.push(4);
ll.push(15);
ll.push(85);
cout << "Given linked list\n";
ll.print();
ll.head = ll.reverse(ll.head);
cout << "\nReversed Linked list \n";
ll.print();
return 0;
}
Time Complexity: O(n) Space Complexity: O(1)
Simpler and Tail Recursive Method:
The implementation of this method is shown below.
For example:
Here Code:
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void reverseUtil(Node* curr, Node* prev, Node** head);
void reverse(Node** head)
{
if (!head)
return;
reverseUtil(*head, NULL, head);
}
void reverseUtil(Node* curr, Node* prev, Node** head)
{
if (!curr->next) {
*head = curr;
curr->next = prev;
return;
}
Node* next = curr->next;
curr->next = prev;
reverseUtil(next, curr, head);
}
Node* newNode(int key)
{
Node* temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}
void printlist(Node* head)
{
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
int main()
{
Node* head1 = newNode(1);
head1->next = newNode(2);
head1->next->next = newNode(3);
head1->next->next->next = newNode(4);
head1->next->next->next->next = newNode(5);
head1->next->next->next->next->next = newNode(6);
head1->next->next->next->next->next->next = newNode(7);
head1->next->next->next->next->next->next->next
= newNode(8);
cout << "Given linked list\n";
printlist(head1);
reverse(&head1);
cout << "\nReversed linked list\n";
printlist(head1);
return 0;
}