Reverse a Doubly Linked List using recursion

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this problem, we are given a doubly linked list, and we need to reverse the given doubly linked list using recursion.

Problem Statement Understanding

Let’s try to understand the problem statement.

Suppose the given doubly linked list is:

  • According to the problem statement, we have to reverse the given doubly linked list.
  • After reversing the doubly linked list, our doubly linked list will look like.

Taking another example, suppose if the given linked list is:

  • In this case, when we reverse the given doubly linked list, our linked list will look like:

Now, I think from the above examples, the problem statement is clear. Let’s see how we can approach it.

What should we do to complete the given task?

  • Remember that a doubly-linked list node has two link parts - next and prev.
  • If we switch the next and prev links for each node of the list, our task of reversal will be done. How is it possible? Let us discuss this in detail in the approach.

Let’s move to the approach section.

Approach

Suppose if the given linked list is:

  • So in this linked list, we can see that there are only 2 nodes, 1 and 2.
  • The prev of 1 is NULL, and the next of 1 is 2. The prev of 2 is 1 and the next of 2 is NULL.
  • Now, to reverse the given doubly linked list, we need to swap the prev and next for all the linked list nodes (As a recursive solution is demanded here, we will do the above process of swapping recursively).
  • Finally, after swapping the prev and next of all the nodes, we will have our reversed doubly linked list.

This is the essence of reversing a doubly linked list. If we just switch the prev and next of each node, the doubly linked list will get reversed.

To see the above approach in more detail, check out the algorithm.

Algorithm

  • Base case - If the head is NULL, return NULL.
  • Otherwise:
    • Create a Node temp = head->next.
    • Now make, head->next = head->prev and head->prev = temp.
    • By doing the previous steps, we are simply just exchanging (or say swapping) the next and prev nodes.
  • Now, if head->prev becomes null, this means that the list has been fully traversed. So, we will simply return the head.
  • In the end, recur for the head->prev.
    • Here, we are recurring for a head->prev instead of the head->next because for every node, prev and next are exchanged. So, to move forward, we will recur as - Reverse(head->prev).
  • By performing the above steps, the doubly linked list will get reversed.

Dry Run

Code Implementation

#include 
using namespace std;

/* Structure of a doubly linked list node */
struct Node {
    int data;
    Node *next, *prev;
};

/* Using this function, we will create a new list node and return the node */
Node* getNode(int data)
{

    Node* new_node = new Node;
    new_node->data = data;
    new_node->next = new_node->prev = NULL;
    return new_node;
}

/* Using this function we will add a node to the head of the linked list */
void push(Node** head_ref, Node* new_node)
{

    new_node->prev = NULL;

    new_node->next = (*head_ref);

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

    (*head_ref) = new_node;
}

/* Using this function we will be reversing the given doubly linked list recursively */
Node* Reverse(Node* node)
{

    if (!node)
        return NULL;

    Node* temp = node->next;
    node->next = node->prev;
    node->prev = temp;

    if (!node->prev)
        return node;

    return Reverse(node->prev);
}

/* Using this function, we will be printing the content of the linked list */
void printList(Node* head)
{
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
}

int main()
{
    Node* head = NULL;
    push(&head, getNode(8));
    push(&head, getNode(6));
    push(&head, getNode(4));
    push(&head, getNode(2));
    cout << "Original doubly linked list before reversing: ";
    printList(head);

    head = Reverse(head);
    cout << "\ndoubly linked list after reversing: ";
    printList(head);
    return 0;
}
public class PrepBytes
{

/* Doubly linked list node structure */ 
static class Node
{
    int data;
    Node next, prev;
};

/* Using this function, we will create a new list node and return the node */
static Node getNode(int data)
{

    Node new_node = new Node();
    new_node.data = data;
    new_node.next = new_node.prev = null;
    return new_node;
}

/* Using this function we will add a node to the head of the linked list */
static Node push(Node head_ref, Node new_node)
{
    
    new_node.prev = null;

    new_node.next = (head_ref);

    if ((head_ref) != null)
        (head_ref).prev = new_node;

    (head_ref) = new_node;
    return head_ref;
}

/* Using this function we will be reversing the given doubly linked list recursively */
static Node Reverse(Node node)
{
    if (node == null)
        return null;

    Node temp = node.next;
    node.next = node.prev;
    node.prev = temp;

    if (node.prev == null)
        return node;

    return Reverse(node.prev);
}

/* Using this function, we will be printing the content of the linked list */
static void printList(Node head)
{
    while (head != null)
    {
        System.out.print( head.data + " ");
        head = head.next;
    }
}

public static void main(String args[])
{
    Node head = null;

    head = push(head, getNode(8));
    head = push(head, getNode(6));
    head = push(head, getNode(4));
    head = push(head, getNode(2));
    System.out.print( "Original doubly linked list before reversing: ");
    printList(head);

    head = Reverse(head);
    System.out.print("\ndoubly linked list after reversing: ");
    printList(head);
}
}

Output

Original doubly linked list before reversing: 2 4 6 8
doubly linked list after reversing: 8 6 4 2

Time Complexity: O(n), as list traversal is needed.

So, in this article, we have tried our best to explain how to reverse a doubly linked list using recursion. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Merge two sorted linked lists (in-place)
Next post How To Iterate LinkedList in Java

Leave a Reply

Your email address will not be published. Required fields are marked *