Linked List: Reverse a Doubly Linked List

Problem Statement:

You are given an DLL you need to reverse the given DLL.

Example

Input:

-> 1 -> 2 -> 3 -> 4
     <-   <-   <- 

Output:

-> 4 -> 3 -> 2 -> 1
     <-   <-   <- 

Solution

The solution is very simple.

We need to swap prev and next pointers for all the nodes.

Then change the prev of the head and change the head pointer to end.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <vector>
#include <stack> 

using namespace std;

class Node 
{ 
    public:
    int data; 
    Node *next; 
    Node *prev; 
}; 
 
void reverse_DLL(Node **head_ref) 
{ 
    Node *temp = NULL; 
    Node *current = *head_ref; 
   
    while (current != NULL) 
    { 
        temp = current->prev; 
        current->prev = current->next; 
        current->next = temp;             
        current = current->prev; 
    } 

    if(temp != NULL ) 
        *head_ref = temp->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; 
} 
 
void print_list(Node *node) 
{ 
    while(node != NULL) 
    { 
        cout << node->data << " "; 
        node = node->next; 
    } 
} 
 
int main() 
{ 
    Node* head = NULL; 
     
    push(&head, 1); 
    push(&head, 2); 
    push(&head, 3); 
    push(&head, 4); 
     
    cout << "Original Linked list" << endl; 
    print_list(head); 
     
    reverse_DLL(&head); 
     
    cout << "\nReversed Linked list" << endl; 
    print_list(head);         
     
    return 0;
} 

Output:

Original Linked list
4 3 2 1
Reversed Linked list
1 2 3 4