Reverse a Singly Linked List in JavaScript (Iteratively and Recursively)

A common interview question you may come across if youre applying for Software Engineer positions (especially at large FAANG types of companies) is to reverse a linked list.

If youre familiar with what linked lists are this problem may seem like a piece of cake. Well not so fast!

Reversing a linked list involves several different steps that need to be implemented in a specific order. So lets start by going over what linked lists actually are and the types of linked lists youre most likely to come across in the wild.

What are Linked Lists?

A linked list is a data structure. Its a collection of elements or nodes stored linearly with each node containing a pointer that references the next node in the list, therefore linking the entire collection of nodes with one another. This is the basic overview of the concept. Now there are several types of linked lists such as singly and doubly-linked lists. Here well just be implementing the first.

Singly-linked lists are a collection of nodes with each node holding a next pointer referencing the following node until the last node's next pointer points to null.

{1, next} => {2, next} => {3, next} => {4, next} => null

Doubly-linked lists are also a collection of nodes though they have a pointer to the next node like singly-linked lists, they also hold a pointer to the previous node.

{prev, 1, next} <=> {prev, 2, next} <=> {prev, 3, next} => null

Iterative Approach

To iteratively reverse a singly linked list, we must adjust the node pointers of each node to point to the previous node in the list. Since a singly linked list only has nodes with next pointers, we need to manually track the previous node before each node we are currently traversing on.

To solve this problem we should be manipulating the node pointers in place and not creating a new linked list.

The following is what our singly linked list nodes will appear as:

Now that we have a visual of what well be working with lets implement our solution in the reverse() function below.

On lines 5-7 were setting several pointers to keep track of the current node, previous node before the current, and next node after current. Then for lines 1015, we loop to perform our reversal by adjusting the node pointers during each iteration to reverse the linked list in place. When reversal is done we break from the loop. On lines 1718 we reset the head to be the last node from the original order of the singly linked list and return a reference to the new head.

Before: {1, next} => {2, next} => {3, next} => {4, next} => nullAfter:  {4, next} => {3, next} => {2, next} => {1, next} => null

Recursive Approach

Weve already seen how we can reverse a list iteratively now lets go over how to reverse a singly linked list recursively.

Well start at the top with the head node to reverse the list then recursively traverse down the call stack until we reach the last node. When we reach the last node, we can then traverse back up the call stack reversing the list by adjusting each nodes next pointer along the way. Once were back at the top since we kept a reference to the last node (the new head) we can just return it giving us a completely reversed list.

Line 35 is our exit condition for when were finished reversing the linked list, we will just return the new head here. Then line 69 is the core of our algorithm. Line 6 is where we are moving downwards on the call stack until we arrive at the end of the list. Lines 7 & 8 is where we adjust our next pointers to reverse the links, and line 9 is where we are returning up the call stack with the evaluated result of reversedHead.

The visual below might help with understanding this logic. It represents how the call stack appears for this problem:

         -----------------CALL STACK-------------------         -(head)(reversedHead)-------------------------         ----------(head)(reversedHead)----------------         -------------------(head)(reversedHead)-------         ---------------------------------------(head)-

In the above visual, each line represents a stack frame that is created for each recursive function call. The top reference to the head is when it is first passed into our recursivelyReverseList() function. The last line represents our base case for when we reach the end of the list. Then the reversal happens when returning back up the call stack with a reference to the new head of the list.

Summary

Learning how to reverse a linked list can be a great exercise for learning common interview problems. It may trip you up plenty (like it did me!) but if you keep at it you might gain a better understanding of this fundamental data structure.

Resources

• Reverse a linked list iterative method

• Reverse a linked list using recursion

• How to Reverse a Singly Linked List the Ultimate Explanation

More content at plainenglish.io