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
isnull
then returnnull
. - 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).
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).