Probelm statement: Reverse a doubly linked list using recursion

A doubly linked list is a data structure where each node has a pointer to the previous node as well as a pointer to the next node in the list. In this problem, we are given a doubly linked list and we need to reverse it using recursion.

The idea behind reversing a doubly linked list using recursion is to recursively swap the next and previous pointers of each node until we reach the end of the list. We start by swapping the next and previous pointers of the head node, and then recursively swap the pointers of the next node until we reach the end of the list.

Once we reach the end of the list, the last node becomes the new head of the reversed list. We need to handle this special case by updating the head pointer to point to the last node of the original list.

By using recursion, we avoid the need to traverse the list multiple times, making this approach more efficient than a non-recursive solution.

### Reverse a doubly linked list in Java

``````class Node {
int data;
Node prev, next;

Node(int data) {
this.data = data;
prev = next = null;
}
}

void reverse(Node node) {
if (node == null) {
return;
}
Node temp = node.next;
node.next = node.prev;
node.prev = temp;
if (node.prev == null) {
return;
}
reverse(node.prev);
}
}
``````

In the above Java code snippet, we define a `Node` class to represent each node in the doubly linked list. Each `Node` has an integer `data` field as well as pointers `prev` and `next` to the previous and next nodes in the list, respectively.

We also define a `DoublyLinkedList` class with a `head` field to point to the first node of the list. The `reverse` method takes a node as input and recursively reverses the list by swapping the `prev` and `next` pointers of each node until we reach the end of the list.

We start by checking if the input `node` is `null`. If it is, we set the `head` to `null` to indicate that the list is empty and return. Otherwise, we swap the `prev` and `next` pointers of the `node`, and then recursively call the `reverse` method with the `prev` node until we reach the end of the list.

Once we reach the end of the list, we update the `head` pointer to point to the last node of the original list (which is now the first node of the reversed list).

### Reverse a doubly linked list in Python

``````class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None

def __init__(self):

def reverse(self, node):
if node is None:
return
temp = node.next
node.next = node.prev
node.prev = temp
if node.prev is None:
return
self.reverse(node.prev)
``````

In the above Python code snippet, we define a `Node` class to represent each node in the doubly linked list. Each `Node` has an integer `data` field as well as pointers `prev` and `next` to the previous and next nodes in the list, respectively.

We also define a `DoublyLinkedList` class with a `head` field to point to the first node of the list. The `reverse` method takes a node as input and recursively reverses the list by swapping the `prev` and `next` pointers of each node until we reach the end of the list.

We start by checking if the input `node` is `None`. If it is, we set the `head` to `None` to indicate that the list is empty and return. Otherwise, we swap the `prev` and `next` pointers of the `node`, and then recursively call the `reverse` method with the `prev` node until we reach the end of the list.

Once we reach the end of the list, we update the `head` pointer to point to the last node of the original list (which is now the first node of the reversed list).

### Reverse a doubly linked list in JavaScript

``````class Node {
constructor(data) {
this.data = data;
this.prev = null;
this.next = null;
}
}

constructor() {
}

reverse(node) {
if (node === null) {
return;
}
let temp = node.next;
node.next = node.prev;
node.prev = temp;
if (node.prev === null) {
return;
}
this.reverse(node.prev);
}
}
``````

In the above JavaScript code snippet, we define a `Node` class to represent each node in the doubly linked list. Each `Node` has an integer `data` field as well as pointers `prev` and `next` to the previous and next nodes in the list, respectively.

We also define a `DoublyLinkedList` class with a `head` field to point to the first node of the list. The `reverse` method takes a node as input and recursively reverses the list by swapping the `prev` and `next` pointers of each node until we reach the end of the list.

We start by checking if the input `node` is `null`. If it is, we set the `head` to `null` to indicate that the list is empty and return. Otherwise, we swap the `prev` and `next` pointers of the `node`, and then recursively call the `reverse` method with the `prev` node until we reach the end of the list.

Once we reach the end of the list, we update the `head` pointer to point to the last node of the original list (which is now the first node of the reversed list).

### Reverse a doubly linked list in Ruby

``````class Node
attr_accessor :data, :prev, :next

def initialize(data)
@data = data
@prev = nil
@next = nil
end
end

def initialize
end

def reverse(node)
if node.nil?
return
end
temp = node.next
node.next = node.prev
node.prev = temp
if node.prev.nil?
return
end
reverse(node.prev)
end
end``````

In the above Ruby code snippet, we define a `Node` class to represent each node in the doubly linked list. Each `Node` has an integer `data` field as well as pointers `prev` and `next` to the previous and next nodes in the list, respectively.

We also define a `DoublyLinkedList` class with a `head` field to point to the first node of the list. The `reverse` method takes a node as input and recursively reverses the list by swapping the `prev` and `next` pointers of each node until we reach the end of the list.

We start by checking if the input `node` is `nil`. If it is, we set the `head` to `nil` to indicate that the list is empty and return. Otherwise, we swap the `prev` and `next` pointers of the `node`, and then recursively call the `reverse` method with the `prev` node until we reach the end of the list.

Once we reach the end of the list, we update the `head` pointer to point to the last node of the original list (which is now the first node of the reversed list).

### Conclusion

In this problem, we were given a doubly linked list and tasked with reversing it using recursion. We achieved this by recursively swapping the next and previous pointers of each node until we reached the end of the list. We then updated the head pointer to point to the last node of the original list, which became the first node of the reversed list.

We provided code solutions to this problem in four different programming languages: Java, Python, JavaScript, and Ruby. Each of the code snippets followed the same basic algorithm and logic, with only minor differences in syntax and language-specific details.

Reversing a doubly linked list using recursion is an efficient approach, as it avoids the need to traverse the list multiple times. It is also a good exercise in recursive problem-solving and linked list manipulation.

#### Written by Shahid

With 10+ years in software engineering, I specialize in blogging and web development. My skills span front-end, back-end, database design, web security, and SEO. Passionate about crafting helpful digital experiences.