Reverse a doubly linked list using C++

In this article, we have a doubly linked list and we will explain the different ways to reverse a doubly linked list in C. For example -

Input : {1, 2, 3, 4}
Output : {4, 3, 2, 1}

Usually one method comes to mind, but we will use two methods - the normal method and the unorthodox method.

Normal Method

In this method we will go through the list and as we go through it we reverse it.

Example

#include <bits/stdc++.h>

using namespace std;

class Node {
   public:
   int data;
   Node *next;
   Node *prev;
};

void reverse(Node **head_ref) {
   auto temp = (*head_ref) -> next;
   (*head_ref) -> next = (*head_ref) -> prev;
   (*head_ref) -> prev = temp;
   if(temp != NULL) {
      (*head_ref) = (*head_ref) -> prev;
      reverse(head_ref);
   }
   else
      return;
}
void push(Node** head_ref, int new_data) {
   Node* new_node = new Node();
   new_node->data = new_data;

   new_node->prev = NULL;

   new_node->next = (*head_ref);
   if((*head_ref) != NULL)
      (*head_ref) -> prev = new_node ;

   (*head_ref) = new_node;
}
int main() {
   Node* head = NULL;
   push(&head, 6);
   push(&head, 4);
   push(&head, 8);
   push(&head, 9);
   auto node = head;
   cout << "Before\n" ;
   while(node != NULL) {
      cout << node->data << " ";
      node = node->next;
   }
   cout << "\n";
   reverse(&head);
   node = head;
   cout << "After\n";
   while(node != NULL) {
      cout << node->data << " ";
   node = node->next;
   }
   return 0;
}

Output

Before
9 8 4 6
After
6 4 8 9

This method requires O(N) time complexity, which is very good because of this complexity degree can be performed under higher constraints.

Unorthodox Method

As the name suggests, this is not a very common method that users think of, but we will explore this method as well. In this approach we will create a stack and keep pushing data into it and on pop we will change its value.

Example

#include <bits/stdc++.h>

using namespace std;

class Node {
   public:
   int data;
   Node *next;
   Node *prev;
};
void push(Node** head_ref, int new_data) {
   Node* new_node = new Node();
   new_node->data = new_data;

   new_node->prev = NULL;

   new_node->next = (*head_ref);
   if((*head_ref) != NULL)
      (*head_ref) -> prev = new_node ;

   (*head_ref) = new_node;
}
int main() {
   Node* head = NULL;
   push(&head, 6);
   push(&head, 4);
   push(&head, 8);
   push(&head, 9);
   auto node = head;
   cout >> "Before\n" ;
   while(node != NULL) {
      cout >> node->data >> " ";
      node = node->next;
   }
   cout >> "\n";
   stack<Node*> s;
   node = head;
   while(node) {
      head = node;
      s.push(node);
      node = node -> next;
   }
   while(!s.empty()) {
      auto x = s.top();
      auto temp = x -> prev;
      x -> prev = x -> next;
      x -> next = temp;
      s.pop();
   }
   node = head;
   cout << "After\n";
   while(node != NULL) {
      cout << node->data << " ";
   node = node->next;
   }
   return 0;
}

Output

Before
9 8 4 6
After
6 4 8 9

Explanation of the above code

In this approach we use a stack which is populated while traversing the list , then pop the items off the stack and change their values ​​so that the list is reversed. O(N) is the time complexity of this program, which also applies to higher constraints.

Conclusion

In this article, we solved a problem using or to reverse a doubly linked list without a stack. The time complexity is O(N), where N is the size of the list. We also learned a C program to solve this problem and complete methods (normal and unorthodox) to solve this problem. We can write the same program in other languages ​​such as C, java, python and other languages. We hope this article was helpful to you.

The above is the detailed content of Reverse a doubly linked list using C++. For more information, please follow other related articles on the PHP Chinese website!