Learn how to reverse a linked list recursively

An algorithm to reverse a single linked list recursively using javascript.

Example

Input: 20 -> 5 -> 30 -> 7 -> 3 Output: 3 -> 7 -> 30 -> 5 -> 20 

Implementation to reverse a single linked list recursively.

• We are going to use a function which will be called recursively, it will take the list head as an input.
• In the function we will check if the head is null then return the head, else if the next element is null then also return the head.
• Else call the same function again and store its output in a temporary variable.
• After this we are going to change the element reference by assign the head to the second next element like this head.next.next = head and setting the next element to null.
• At the end return the temp variable.

Check out the below image for the working of the above implementation.

let reverseRecursively = (head) => { if(head === null){ return head; } if(head.next === null){ return head; } let newHeadNode = reverseRecursively(head.next); // change references for middle chain head.next.next = head; head.next = null; // send back new head node in every recursion return newHeadNode; } 

Input: let ll = new linkedlist(); ll.append(20); ll.append(5); ll.append(30); ll.append(7); ll.append(3); let head = ll.getHead(); //20 -> 5 -> 30 -> 7 -> 3 console.log(reverse(head)); Output: 3 -> 7 -> 30 -> 5 -> 20 

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

Time and Space complexity

• We are calling each element of the list through the function, so Time complexity is O(n).
• We are calling function recursively, so Space complexity is O(n).