Reverse Linked List (LeetCode) – Iterative and recursive implementation8 min read

Happy New Year, everyone! On the very first day of 2020, let’s jump to a problem that has been asked all the time during the interview – Reverse A Linked List. In this article, we will tackle this problem, but first, if you don’t know what is linked list, check this article before we proceed.

If you want to take a try before we jump into the solution, feel free to redirect this link to do it on LeetCode.

Given a singly linked list, and you have to reverse it, for example:

Input: 1->2->3->4->5->NULL 
Output: 5->4->3->2->1->NULL

This question can be solved by either iteratively or recursively and we gonna do them both in JavaScript.

Iterative method

The procedure to solve this problem by the iterative method can be constructed as follow:

• First, we just need to initialize one pointer, prev to NULL and one another variable curr points to head.
• Inside the loop, we need to create a variable nextNode which is assigned to the pointer of the next node after each iteration starting from the head.
• Then we assign the next pointer of the curr to the prev.
• We assign the value of the curr to the prev variable.
• After that, we assign the value of the nextNode to the curr.
• Once our curr variable reaches the last element of the list, we terminate the loop and return prev.

Now let’s do it in JavaScript. First, we create a function reverseList which takes one parameter head, then inside this function, we create 2 variables, prev with the value of NULL and the head value is assigned to the curr variable.

/**
 Definition for singly-linked list.
 function ListNode(val) {
 this.val = val;
 this.next = null;
 }
 / /*
 @param {ListNode} head
 @return {ListNode}
 */
 var reverseList = function(head) {
     let prev = null;
     let curr = head;
 }; 

The code in the comment is the definition for a singly linked list, it works as a constructor when we create a new node inside the reverseList function.

Now, we create a while loop, we do actual work inside this loop. We create a new variable nextNode which helps us point to the next node of the current node in each iteration. Then we swap values, the curr.next typically points to the next node of the current node, but we change it to point to the prev node, then we take the value of the head and assign it to the prev, and the curr now points to the nextNode, the loop will terminate when the head pointer reaches to NULL:

     while(curr != null){
         let nextNode = curr.next;
         curr.next = prev;
         prev = curr;
         curr = nextNode;
     }

And when we have done, everything we need is to return the prev, which is the pointer of the list has been reversed, the complete code is shown below:

var reverseList = function(head) {
     let prev = null;
     let curr = head;
     while(curr != null){
         let nextNode = curr.next;
         curr.next = prev;
         prev = curr;
         curr = nextNode;
     }
     return prev
 };

I think it’s still a little ambiguous up to this point; let’s clarify it a little more; suppose we have a singly linked list with a structure as such 1 -> 2 -> 3 -> NULL and want to reverse it to 3 -> 2 -> 1 -> NULL:

prev = null
curr = head
On the first iteration:
   nextNode = curr.next <=> nextNode = 2
   curr.next = prev <=> curr.next = NULL (before points to 2, then now it points backward to NULL)
   prev = curr <=> prev = 1 
   curr = nextNode <=> head = 2
After the first iteration, now we have:
   nextNode = 2
   curr.next = NULL
   prev = 1
   curr = 2 (after the first iteration, now the curr is the second node)

On the second iteration:
   nextNode = curr.next <=> nextNode = 3
   curr.next = prev <=> curr.next = 1 (before it points to the third now, but now we make it points back to the 1st node)
   prev = curr <=> prev = 2
   curr = nextNode <=> curr = 3 
After the second iteration, now we have:
   nextNode = 3
   curr.next = 1
   prev = 2
   curr = 3 (now the curr is the third node)

On the third iteration:
   nextNode = curr.next <=> nextNode = NULL
   curr.next = prev <=> curr.next = 2 (before it points to the last node, which is NULL, now it points to the second node)
   prev = curr <=> prev = 3
   curr = nextNode <=> curr = NULL
After the third iteration, now we have:
   nextNode = NULL
   curr.next = 2
   prev = 3
   curr = NULL

On the fourth iteration:
   Because the condition curr != NULL is no longer true (which means we have reached the last node), then this loop is terminated.
   

Recursive Approach

The recursive approach is a little trickier than the iterative method. But the general idea is listed as follow:

• Start from the head and assign it to the curr variable
• If curr is NULL, return curr
• Create a variable has a role as a pointer and do the recursive call to the next curr
• If the curr.next is NULL, which means it is the last node of our list, so we make it as the head of our list, as we are doing the reverse linked list
• We recursively traverse the list
• Set curr.next.next to curr
• Set curr.next to NULL.

To help us better envision, first, let’s take a look at some visualized examples before we get into some code. Suppose that we have a singly linked list 1->2->3->4->NULL and want it will be 4->3->2->1->NULL after our reverse function:

For the first recursive call, we set curr as head, then we check whether curr and curr.next is null or not, because both of them are not null, we do another recursive call:

On the second recursive call, we change our curr to the second node, and we observe that the curr and curr.next are both still not null, then we proceed another recursive call:

On the third recursive call is pretty much the same as the first and the second want, now the curr is the third node and curr and curr.next are still not null:

On this recursive call, we have seen something different. The curr node is in the last node because curr.next is null, then it is now our new head as in our base condition:

After the fifth recursive call, now our head is the fourth node and we recursively traverse the list and make the third node as our curr, also we set the curr.next.next which initially pointed to null in this picture; now it points back curr itseft and curr.next to null.

On the sixth recursive call, things go pretty similar to the last one. Now we already see that the last node now points to the third node, and in a similar manner, the third node now points back to the second node:

Here we go again:

And finally, we have a reversed linked list by using a recursive function:

The code can be translated pretty much the same as we have discussed above:

/**
 Definition for singly-linked list.
 function ListNode(val) {
 this.val = val;
 this.next = null;
 }
 / /*
 @param {ListNode} head
 @return {ListNode}
 */
var reverseList = function(head) {
    let curr = head;
    if (curr == null || curr.next == null) return curr;
    let pointer = reverseList(curr.next);
    curr.next.next = curr;
    curr.next = null;
    return pointer;
};

First, we define a curr as head, after that we have a base case here, if curr is null or curr.next is null, we return curr. We have another variable pointer which does the recursive call consecutively until the base case is met. And once curr.next is null, which means we reach the end of our list, we will do some next steps, set curr.next.next to curr and curr.next to null. Finally, we return this variable pointer which is what we should return.