# 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->NULLOutput: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 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 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:

/**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)returncurr; let pointer = reverseList(curr.next); curr.next.next = curr; curr.next = null;returnpointer; };

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.

## Facebook Comments