Reverse a Doubly Linked List | Linked list articles | PrepBytes Blog

popup_image

Get free ebooK with 50 must do coding Question for Product Based Companies solved

Fill the details & get ebook over email

PrepBytesJuly 26, 2021February 25, 2022

Last Updated on February 25, 2022 by Ria Pathak

Reverse a Doubly Linked List

In this problem, we will be given a doubly linked list as input and we need to reverse it.
Let the given input be:

Input

Then the output will be:

Output

Approach #1:

This approach is similar to reversing data in an array. We initialize 2 pointers one at starting and the other at end of the linked list and swap their data till both of them do not cross each other or become equal.

NOTE : This approach may not be a good approach because a node might contain more than one data and then we would need to swap all of them hence approach #2 is a more preferred approach.

Time Complexity : O(n), but we need to loop the list twice. First, we will get the address of the last node then we will loop the list to reverse it.

Space Complexity : O(1).

Approach #2:

The method to reverse a doubly-linked list is very trivial. As we know that we could access the previous as well as the next node from a given node, we could easily achieve reversal of this list by swapping the previous as well as next pointers of all nodes iteratively.

Code Implementation :

Reverse a Doubly Linked List

C++

#include 
using namespace std;

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

void add_at_begin(Node** head, int &x)
{
 
    Node* new_node = new Node();//create node of doubly linked 
   //list
 
    //assign the data entered by user
    new_node->data = x;
 
    // node is inserted in beginning so, prev will always 
    // be NULL
    new_node->prev = NULL;
 
    //the node created is inserted at beginning so we need to
    //connect it with previous head
    new_node->next = (*head);
     
    // change the head to the current node’s address
    if ((*head) != NULL)
        (*head)->prev = new_node;
 
    (*head) = new_node;
}
void print_list(Node* node)
{
    while (node != NULL)
    {
        cout << node->data << ",";
        node = node->next;
    }
}
void reverse_list(Node **head)
{
    Node *temp = NULL;
    Node *current = *head;
    
    while (current != NULL)
    {
        // swap prev as well as next of all nodes 
        temp = current->prev;
        current->prev = current->next;
        current->next = temp;            
        current = current->prev;
    }
     
    //check if list is empty or if it has only one node
    // before updating head
    if(temp != NULL )
        *head_ref = temp->prev;
}
 
int main()
{
    Node* head = NULL;
 
    add_at_begin(&head, 17);
    add_at_begin(&head, 13);
    add_at_begin(&head, 1);
    add_at_begin(&head, 7);
    add_at_begin(&head, 2);
 
    reverse_list(head);
    
    print_list(head);
 
    return 0;
}

Output
17,13,1,7,2

Time Complexity – O(n)
[forminator_quiz id=”3438″]
So, in this blog, we have tried to explain how you can reverse a doubly linked list in the most efficient way. If you want to practise more questions on a doubly-linked list, feel free to do so at Prepbytes Linked List.

Leave a Reply Cancel reply