# Reverse Linked List (LeetCode) – Iterative and recursive implementation7 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.

```/**
function ListNode(val) {
this.val = val;
this.next = null;
}
/ /*
@return {ListNode}
*/
let prev = null;
}; ```

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;
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 structure as such `1 -> 2 -> 3 -> NULL` and want to reverse it to `3 -> 2 -> 1 -> NULL`:

```prev = null
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 forth 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:

```/**
function ListNode(val) {
this.val = val;
this.next = null;
}
/ /*
@return {ListNode}
*/
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 then we have a base case here, if `curr` is null or `curr.next` is null, we return `curr`. We have another variable `pointer` which do the recursive call consecutively until the base case is met. And once `curr.next` is null which means we reach to 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.  