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).