How To Reverse A Linked List In Javascript Recursively and Iteratively

Reversing a singly a linked list using both iterative and recursive methods is a common algorithm problem asked in programming job interviews, coding competitions, and online coding challenge platforms such as leetcode and hackerrank .

In this article, we will discuss the question through JavaScript and examine each step of solving the question.

Let's get started.

How To Reverse A Singly Linked List In Javascript

As we've mentioned above, we can reverse a singly linked list in two ways, iteratively and recursively. These methods differ both in the method of implementation and in their running performance. Let's see them.

Iterative Method For Reversing A Singly Linked List

This method involves reversing each node step by step starting from the head, and then it returns the head of the reversed singly linked list. It has a time complexity of O(n) and a space complexity of O(1).

function reverse(head) {
  let prev = null;
  let current = head;

  while (current) {
    let next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
  return prev;
}

Let's explain the each steps:

• prev represents the reversed portion of the linked list and current represents the node being processed
• We iterate through the linked list using a while loop, loop runs until the current node becomes null, which means there is no node that will be reversed.
• Inside the loop we use a temporary variable ``next``` to store the tail of the linked list so as not to lose the connection., We then reverse the current node by linking it to the prev node.
• We then move both prev and current forward by setting prev to current and current to next nodes, respectively.
• Finally, we return prev, which is the head node of the reversed singly linked list.

Recursive Method For Reversing A Singly Linked List

In the recursive function, firstly the new head node is reached and existing links are reversed later. This method works with O(n) space and time complexity due to the recursive call stack.

function reverseRecursive(head) {
  if (!head.next) {
    return head;
  }
  let newHead = reverseRecursive(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}

Let's explain how it works:

• It works by recursively invoking itself with the next node as a parameter. it reaches the end of the linked list, which is the new head of the reversed linked list.
• Once the last node has been found, the function starts reversing the links between the nodes. head.next.next = head; links the current node (which is the node before the new head node) to the new head node.
• Once the last node has been found, the function starts reversing the links between the nodes. head.next.next = head; links the current node (which is the node before the new head node) to the new head node.
• The line head.next = null; sets the link to the previous node to null, removing the link before it is reversed.
• Finally, the function returns the new head node of the reversed linked list.

Conclusion

In this post, we have created a solution for the one of the most popular coding questions, how to reverse a singly linked list with javascript in two ways, iteratively and recursively and provide explanation with examples.

Thank you for reading.