Reverse a doubly linked list using recursion

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;
    }
}

class DoublyLinkedList {
    Node head;

    void reverse(Node node) {
        if (node == null) {
            head = null;
            return;
        }
        Node temp = node.next;
        node.next = node.prev;
        node.prev = temp;
        if (node.prev == null) {
            head = node;
            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

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def reverse(self, node):
        if node is None:
            self.head = None
            return
        temp = node.next
        node.next = node.prev
        node.prev = temp
        if node.prev is None:
            self.head = node
            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;
    }
}

class DoublyLinkedList {
    constructor() {
        this.head = null;
    }

    reverse(node) {
        if (node === null) {
            this.head = null;
            return;
        }
        let temp = node.next;
        node.next = node.prev;
        node.prev = temp;
        if (node.prev === null) {
            this.head = node;
            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

class DoublyLinkedList
  attr_accessor :head

  def initialize
    @head = nil
  end

  def reverse(node)
    if node.nil?
      @head = nil
      return
    end
    temp = node.next
    node.next = node.prev
    node.prev = temp
    if node.prev.nil?
      @head = node
      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.