Hello all! Today I would like to walk through my iterative solution of how to reverse a linked list. But first, *what is a linked list, you ask?*

According to Wikipedia:

In computer science, a

linked listis a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence.

A linked list is made up of nodes. Each node composes of two things: 1) some data value and 2) a pointer to the next node. The next node in a linked list can be accessed via the `next`

property on the current node. See a representation of a short linked list below:

To simplify, I will refer to the first node as `n1`

and the second `n2`

. The **head** of the linked list in the diagram above is `n1`

and the **tail** is `n2`

. A tail in a linked list will always point to `null`

.

Let’s now get on with our problem:

Instruction: Reverse a singly linked list.

Ex.Input:1->2->NULL |Output:2->1->NULL

We can solve this problem by having the `head`

(`n1`

) point to `null`

, then have `n2`

point to `n1`

. Which would give us the following:

Sounds easy in theory, but how will this be implemented? The trick here is to keep track of all the moving pieces. Let’s take things one step at a time.

- Create a variable called
`previous`

, initializing it to`null`

.

`let previous = null;`

2. We want our `head`

(`n1`

) to point to `previous`

. However, if we simply do so via `head.next = previous`

, we would lose track of `n2`

! If these nodes were people, it is as if `n1`

is holding `n2`

’s hand. If `n1`

lets go (via pointing to something else), then `n2`

can drift away into the void, and there would be no way for us to refer back to it!

Therefore, we need to keep track of the second node before pointing the `head`

to `previous`

. We can do so by assigning the second node to a variable, let’s call it `nextNode`

. Remember, right now `n1`

still points to `n2`

, so we can access `n2`

by calling `head.next`

.

`let nextNode = head.next;`

3. Now we can set the pointer of `head`

to `previous`

without worrying that we won’t have access to the second node.

`head.next = previous;`

4. The next step is to point `n2`

to `n1`

, to do so we will need to reassign some variables.

Since we won’t need access to `null`

anymore, our current `head`

will be the new `previous`

, and `nextNode`

will be our new `head`

. How this looks like in code and diagram:

`previous = head;`

head = nextNode;

5. Repeat steps 2 to 4 while the `head`

is not `null`

.

The next iteration of the above steps would have `n2`

point to `n1`

, which would end up looking like the following:

We have our new reversed linked list! The `head`

variable now points to `null`

which indicates that this is where we should end our iterations. All we would have to do is to return `previous`

, which now references our new linked list. (Side note: the second `null`

is now not associated with our linked list, so we can disregard it).

The process in code:

/**

* Definition for singly-linked list.

* function ListNode(val, next) {

* this.val = (val===undefined ? 0 : val)

* this.next = (next===undefined ? null : next)

* }

*/

/**

* @param {ListNode} head

* @return {ListNode}

*/var reverseList = function(head) {

let previous = null;

while (head !== null) {

let nextNode = head.next;

head.next = previous;

previous = head;

head = nextNode;

}

return previous;

};

There you have it!

If you would like to attempt this problem, click here to try it on Leetcode.

If you would like more animated visuals of this problem, check out this Terrible Whiteboard video!