How to reverse a linked list?

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.

Reverse

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.

Reverse

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:

Reverse

Reverse

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.

Reverse

For example:

Reverse

Reverse

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:

Reverse

Reverse

Reverse

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;
}

Recommended Articles:

  1. Traversal in Circular Linked List
  2. How to split a circular linked list into two halves?
  3. C++ program to insert in a sorted circular linked list?
  4. Insertion in Doubly Linked List
  5. Deletion in Doubly Linked List
  6. How to reverse a doubly linked list?
  7. QuickSort on Doubly Linked List
  8. Merge Sort for Doubly Linked List
  9. How to reverse a string using stack?
  10. Insertion in Circular Singly Linked List
  11. How to swap nodes in a linked list without Swapping data?
  12. How to write C functions that modify head pointer of a Linked List?
  13. Find Length of a Linked List (Iterative and Recursive)?
  14. A Programmer’s approach of looking at Array vs. Linked List
  15. Deletion in Linked List
  16. How to delete a node in a linked list at a given Location?
  17. Insertion in Linked List
  18. Differences between Arrays and Linked Lists?
  19. Introduction to Linked List

References:

Help Me Please: If you found any error in the content or example please let us know by comment also write your suggestion or if any doubt in the concept please feel free to write us in the comment section.

Practice your Code online here

(Visited 83 times, 1 visits today)

0 0 vote
Article Rating
Subscribe
Notify of
7 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
trackback

[…] How to reverse a linked list? […]

trackback

[…] How to reverse a linked list? […]

trackback

[…] How to reverse a linked list? […]

trackback

[…] How to reverse a linked list? […]

trackback

[…] How to reverse a linked list? […]

trackback

[…] How to reverse a linked list? […]

You cannot copy content of this page
Scroll Up
7
0
Would love your thoughts, please comment.x
()
x

  • Name

  • Minimum length of 8 characters.