Last Updated on November 24, 2023 by Ankit Kochar

Reversing a doubly linked list using recursion is a fascinating problem in computer science and programming. A doubly linked list is a linear data structure where each node contains a reference to the previous and next nodes, allowing traversal in both directions. Reversing this data structure involves changing the direction of pointers, essentially flipping the list.

Recursion, a powerful technique in programming, involves breaking down a problem into smaller sub-problems, solving each sub-problem, and combining the results to solve the larger problem. When applied to reversing a doubly linked list, recursion offers an elegant and efficient solution, providing a deeper understanding of both data structures and recursive algorithms.

## How to Reverse a Doubly Linked List Using Recursion?

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

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.

- Create a Node
- 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)**.

- Here, we are recurring for a
- By performing the above steps, the doubly linked list will get reversed.

### Dry Run

### Code Implementation

#include <stdio.h> #include <stdlib.h> // A Doubly Linked List Node struct Node { int data; struct Node *next, *prev; }; // Utility function to push a node at the beginning of the doubly linked list void push(struct Node** head_ref, int new_data) { struct Node* new_node = (struct Node*) malloc(sizeof(struct 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; } // Helper function to print nodes of a doubly linked list void printList(struct Node *node) { while(node!=NULL) { printf("%d ", node->data); node = node->next; } } // Function to swap `next` and `prev` pointers of the given node void swap(struct Node* node) { struct Node* prev = node->prev; node->prev = node->next; node->next = prev; } // Recursive function to reverse a doubly-linked list void reverse(struct Node** headRef, struct Node* curr) { // last node if (curr->next == NULL) { // swap `next` and `prev` pointers for the current node swap(curr); // update head *headRef = curr; return; } // swap `next` and `prev` pointers for the current node swap(curr); // recur with the next node reverse(headRef, curr->prev); } // Function to reverse a doubly-linked list void reverseDDL(struct Node** headRef) { // base case if (*headRef == NULL) { return; } // stores the previous node and the current node struct Node* curr = *headRef; // pass current and previous node information in the recursion itself reverse(headRef, curr); } int main() { /* Start with the empty list */ struct Node* head = NULL; push(&head, 2); push(&head, 7); push(&head, 1); push(&head, 13); push(&head, 17); printf("\n Initial linked list before reversing: "); printList(head); reverseDDL(&head); printf("\n Resultant reversed linked list: "); printList(head); getchar(); }

#include <bits stdc++.h=""> 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); } }

# Structure of a doubly linked list node class Node: def __init__(self, data): self.data = data self.next = None # Using this function, we will create a new list node and return the node def getNode(data): # allocate space new_node = Node(data) new_node.data = data new_node.next = new_node.prev = None return new_node # Using this function we will add a node to the head of the linked list def push(head_ref, new_node): new_node.prev = None new_node.next = head_ref if (head_ref != None): 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 def Reverse(node): if not node: return None temp = node.next node.next = node.prev node.prev = temp if not node.prev: return node return Reverse(node.prev) # Using this function, we will be printing the content of the linked list def printList(head): while (head != None) : print(head.data, end = " ") head = head.next if __name__=='__main__': head = None head = push(head, getNode(8)) head = push(head, getNode(6)) head = push(head, getNode(4)) head = push(head, getNode(2)) print("Original doubly linked list before reversing: ", end = "") printList(head) head = Reverse(head) print("\ndoubly linked list after reversing: ", end = "") 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.

[forminator_quiz id=”5369″]

**Conclusion**

Reversing a doubly linked list using recursion is a stimulating problem that combines the concepts of linked data structures and recursive algorithms. Understanding this process not only enhances one’s grasp of data structures but also sharpens problem-solving skills in programming.

Through this article, we’ve explored the elegance and functionality of using recursion to reverse a doubly linked list. While recursion might not always be the most efficient solution in every context, its application in this scenario showcases its power and beauty in solving problems involving linked structures. This approach offers programmers an alternative perspective and a deeper appreciation for both recursion and linked lists.

## FAQ Related to Reverse a Doubly Linked List:

Here are some FAQs related to Reverse a Doubly Linked List.

**1. Why use recursion to reverse a doubly linked list?**

Recursion simplifies the reversal process by breaking it into smaller, manageable tasks. It’s an intuitive way to tackle the problem, especially when dealing with linked structures like doubly linked lists. It often results in concise and elegant code.

**2. What are the steps involved in reversing a doubly linked list using recursion?**

The basic steps include:

– **Defining base cases:** Identify the terminating conditions for recursion (e.g., reaching the end of the list).

– **Reversing the pointers:** Swap the previous and next pointers for each node in the list.

– **Recursively call the function:** Traverse through the list, altering the pointers until the reversal is complete.

**3. What are the advantages and disadvantages of using recursion for this task?**

Advantages include elegant code structure and ease of understanding. However, recursion may consume more memory due to function calls, and in some cases, it might be less efficient than iterative methods.