How to reverse a doubly linked list?

It is easier to reverse a double-linked list than it is to reverse a single linked list. This operation reverses the nodes in the list of double links, making the first node the last node and the last node the first node.

Reverting a doubly linked list is an important operation. Here we swap the previous and next pointers for all nodes, as well as the head and tail pointers.

reverse

The following C ++ implementation shows a list of reverse double links.

For example:

reverse

reverse

Here, the left and right pointers are swapped and moved towards each other until they meet or intersect. Then the first and last nodes are swapped.

Here Code:

#include <iostream>
using namespace std;
struct Node {
   int data;
   struct Node *prev, *next;
}; 
Node* newNode(int val){
   Node* temp = new Node;
   temp->data = val;
   temp->prev = temp->next = nullptr;
   return temp;
}
void displayList(Node* head){
   while (head->next != nullptr) {
      cout << head->data << " <==> ";
      head = head->next;
      }
   cout << head->data << endl;
}
void insert(Node** head, int node_data){
   Node* temp = newNode(node_data);
   temp->next = *head;
   (*head)->prev = temp;
   (*head) = temp;
}
void reverseList(Node** head){
   Node* left = *head, * right = *head;
   while (right->next != nullptr)
   right = right->next;
   while (left != right && left->prev != right) {
      swap(left->data, right->data);
      left = left->next;
      right = right->prev;}
}
int main(){
   Node* headNode = newNode(5);
   insert(&headNode, 4);
   insert(&headNode, 3);
   insert(&headNode, 2);
   insert(&headNode, 1);
   cout << "Original doubly linked list: " << endl;
   displayList(headNode);
   cout << "Reverse doubly linked list: " << endl;
   reverseList(&headNode);
   displayList(headNode);
   return 0;
}

Complexity Analysis:

  • Time Complexity: O(N), Where N is the number of nodes in the double linked list.
  • Auxiliary Space: O(1)

Recommended Articles:

  1. Insertion in Doubly Linked List
  2. Deletion in Doubly Linked List
  3. QuickSort on Doubly Linked List
  4. How to reverse a string using stack?
  5. How to reverse a 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 82 times, 1 visits today)

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

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

trackback

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

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

  • Name

  • Minimum length of 8 characters.