fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. // Doubly Linked List Node structure
  6. struct DLLNode {
  7.     int data;
  8.     DLLNode* next;
  9.     DLLNode* prev;
  10.     DLLNode(int x) : data(x), next(nullptr), prev(nullptr) {}
  11. };
  12.  
  13. class Solution {
  14. public:
  15.     // Function to reverse a doubly linked list
  16.     DLLNode* reverseDLL(DLLNode* head) {
  17.         if (head == nullptr || head->next == nullptr) 
  18.             return head;
  19.  
  20.         DLLNode *prev = nullptr, *current = head;
  21.  
  22.         while (current != nullptr) {
  23.             // Swap next and prev pointers
  24.             prev = current->prev;
  25.             current->prev = current->next;
  26.             current->next = prev;
  27.  
  28.             // Move to the next node (which is now in prev)
  29.             current = current->prev;
  30.         }
  31.  
  32.         // Prev will be at the last node before reversal
  33.         // So prev->prev will be the new head
  34.         return prev->prev;
  35.     }
  36. };
  37.  
  38. // Helper function to create DLL from vector
  39. DLLNode* createDLL(vector<int>& arr) {
  40.     if (arr.empty()) return nullptr;
  41.  
  42.     DLLNode* head = new DLLNode(arr[0]);
  43.     DLLNode* current = head;
  44.  
  45.     for (int i = 1; i < arr.size(); i++) {
  46.         current->next = new DLLNode(arr[i]);
  47.         current->next->prev = current;
  48.         current = current->next;
  49.     }
  50.  
  51.     return head;
  52. }
  53.  
  54. // Helper function to print DLL forward
  55. void printForward(DLLNode* head) {
  56.     DLLNode* current = head;
  57.     while (current != nullptr) {
  58.         cout << current->data;
  59.         if (current->next != nullptr)
  60.             cout << " <-> ";
  61.         current = current->next;
  62.     }
  63.     cout << endl;
  64. }
  65.  
  66. // Helper function to print DLL backward
  67. void printBackward(DLLNode* tail) {
  68.     DLLNode* current = tail;
  69.     while (current != nullptr) {
  70.         cout << current->data;
  71.         if (current->prev != nullptr)
  72.             cout << " <-> ";
  73.         current = current->prev;
  74.     }
  75.     cout << endl;
  76. }
  77.  
  78. // Helper function to delete DLL
  79. void deleteDLL(DLLNode* head) {
  80.     while (head != nullptr) {
  81.         DLLNode* temp = head;
  82.         head = head->next;
  83.         delete temp;
  84.     }
  85. }
  86.  
  87. int main() {
  88.     Solution sol;
  89.  
  90.     // Test Case 1: Normal case
  91.     vector<int> arr1 = {1, 2, 3, 4, 5};
  92.     DLLNode* dll1 = createDLL(arr1);
  93.     cout << "Original DLL: ";
  94.     printForward(dll1);
  95.  
  96.     DLLNode* reversed1 = sol.reverseDLL(dll1);
  97.     cout << "Reversed DLL: ";
  98.     printForward(reversed1);
  99.     cout << "Backward traversal: ";
  100.     printBackward(reversed1);
  101.     deleteDLL(reversed1);
  102.  
  103.     // Test Case 2: Single node
  104.     vector<int> arr2 = {10};
  105.     DLLNode* dll2 = createDLL(arr2);
  106.     cout << "\nOriginal DLL (single node): ";
  107.     printForward(dll2);
  108.  
  109.     DLLNode* reversed2 = sol.reverseDLL(dll2);
  110.     cout << "Reversed DLL: ";
  111.     printForward(reversed2);
  112.     deleteDLL(reversed2);
  113.  
  114.     // Test Case 3: Empty list
  115.     vector<int> arr3 = {};
  116.     DLLNode* dll3 = createDLL(arr3);
  117.     cout << "\nEmpty DLL: ";
  118.     printForward(dll3);
  119.  
  120.     DLLNode* reversed3 = sol.reverseDLL(dll3);
  121.     cout << "Reversed DLL: ";
  122.     printForward(reversed3);
  123.     deleteDLL(reversed3);
  124.  
  125.     return 0;
  126. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Original DLL: 1 <-> 2 <-> 3 <-> 4 <-> 5
Reversed DLL: 5 <-> 4 <-> 3 <-> 2 <-> 1
Backward traversal: 5

Original DLL (single node): 10
Reversed DLL: 10

Empty DLL: 
Reversed DLL:
https://ideone.com/pb7fmw
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!