Recursively reverse a doubly linked list

Learn how to recursively reverse a doubly linked list in javascript.

Example

Input:
10 -> 20 -> 30 -> 40 -> 50

Output:
50 -> 40 -> 30 -> 20 -> 10

Implementation for recursively reversing a doubly linked list

  • We will create a function which will iterate the doubly linked list in previous direction by calling it self recursively to reverse it.
  • In this function we will check if node is null then return null.
  • Else swap the pointers of the node like convert next node to previous and vice versa.
  • If the prev is null for current node then return the node, else call the function recursively with previous node.

Check out the below image for better understanding. (It works same but in next direction).
Recursively reverse doubly linked list

let reverseDLL = (node) => {
  //If current node is empty 
  //Return null
  if(node === null){
    return null;
  }
  
  //Swap the pointers
  let temp = node.next;
  node.next = node.prev;
  node.prev = temp;
  
  //If no previous node 
  //Return the node
  if(node.prev === null){
    return node;
  }
  
  //Recursively call the function
  return solution4(node.prev);
}
Input:
let dll = new doubleLinkedList();
dll.append(10);
dll.append(20);
dll.append(30);
dll.append(40);
dll.append(50);
let head = dll.getHead();
reverseDLL(head);

Output:
//Head (Next nodes)
50 -> 40 -> 30 -> 20 -> 10

//Tail (Prev nodes)
50 <- 40 <- 30 <- 20 <-10

Time complexity: O(n).
Space complexity: O(n).