Reversing a Linked List
Tags: javascript, codenewbie, todayilearned, tutorial
Published: 2019-10-14 14:51:55

#### A Linked List Problem

I'm learning about [Linked Lists](https://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked%20Lists/linked%20lists.html) and trying my hand at my first linked list problems. Here's a basic one that I want to focus on today.

```
Task: Reverse a singly linked list.

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

*** 
####Failed First Tries
Remember the last time I blogged about [reversing strings and integers](https://dev.to/jenshaw/reversing-an-integer-mathematically-fmg)? I mentioned then that the first time I attempted an integer reversal, I approached it the same way I did with strings and arrays, which didn't work out as great as I would've liked. As per my usual habit, I made a similar mistake here with reversing a linked list.

I started by thinking I'd use the old 'pop' and 'push' approach and realized almost immediately that that just wasn't going to work with this data structure. With singly-linked lists, just to pop or remove the last node would involve traversing the entire length of the linked list, from head to tail, one node at a time. And then, there was a second partial journey to consider. Starting once again from the head of the list, I'd have to re-traverse until I found the appropriate place to re-insert the node. That means, for each and every node I wanted to move, I had to traverse the list at least one and a half times, and that could take forever if your list happened to be just a few nodes too long. It seemed an awfully redundant approach that just didn't make great sense. I was sure there was a better way to go about it.

And there was. Unfortunately, though, I didn't quite figure it out on my own. Ah well.

After about a half-hour of honest effort, I looked up the solution, which I admittedly couldn't understand, but later also found a great [video explanation](https://www.youtube.com/watch?v=O0By4Zq0OFc) by Back to Back SWE that helped clarify my confusion.
 
*** 
####A Step By Step Solution Explanation

The video covers two solutions, one iterative and the other recursive, but I'm just going to focus on explaining the iterative solution for now.

I'll set this explanation up in three stages:

```javascript
function reverseList(head) {
  // Stage 1: The Setup
  let prev = null;
  let curr = head;
  let temp = null;

  while (curr != null) {
    // Stage 2: The Reversal
    temp = curr.next;
    curr.next = prev;

    // Stage 3: The Shift (Variable Reassignment)
    prev = curr;
    curr = temp;
  }

  return prev;
}
```

***
##### Stage One
In the first stage, I'll have three variables:
* `curr` to keep track of the *current* node starting at the head of the list,
* `prev` to track the node previous to the `curr` and is null only for now because there's no attached node prior to `curr` at the moment, and finally...
* `temp`, a temporary container for the node `curr` presently points to. I won't assign anything to it just yet, so for now, it'll be null.

![linked list with node 1 assigned to curr, null assigned to prev, and null assigned to temp variables](https://thepracticaldev.s3.amazonaws.com/i/rxp7os9opcz9cptvp1oj.png)

***

##### Stage Two
At the second stage, we'll open a while loop, during which we'll be re-arranging the nodes.

Keep in mind that with every loop, `curr` is going to move up the nodes in the list. As `curr` moves forward node by node, it'll eventually reach null, the end of the list, and that will break the while loop.

At the first line of the loop, we'll assign `curr.next`, the node following `curr`, to our variable, `temp`. 

![node 2 as curr dot next, assigned to temp](https://thepracticaldev.s3.amazonaws.com/i/1zdswamrnd6lag5lwzf8.png)

It is `temp`'s job to help us keep that particular node and the connecting nodes thereafter safe and within reach. Why is that important? Because we're about to sever that node from `curr`, and we don't want to lose it.

![Dog on boat detaching a rope attached to a person]
(https://media.giphy.com/media/Mr0t48ZNCfJGo/giphy.gif)


On the following line, by assigning `prev` to `curr.next`, we direct `curr`'s only pointer towards `prev`, thus breaking the link to what used to be our old `curr.next` node as well as the rest of the list.

![prev, currently null, assigned as curr dot next](https://thepracticaldev.s3.amazonaws.com/i/t9ut5kefdfhlzt9pal1p.png)
![breaks link from node 1 to node 2](https://thepracticaldev.s3.amazonaws.com/i/yo3gxrb7mwl1eqdek1v2.png)
Good thing we were prepared and kept that node secured in `temp`!

![Whew](https://media.giphy.com/media/3krrjoL0vHRaWqwU3k/giphy.gif)
***
##### Stage Three
One last thing before we complete this loop. In preparation for the next loop, we have to shift our variables over by one node. The current node is now `prev`, and `curr` is the head of our severed list in `temp`.

![node 1 becomes prev, node 2 becomes curr](https://thepracticaldev.s3.amazonaws.com/i/mp47p03kg5iya56bmm86.png)
***

You might notice that we now essentially have two separate lists, 
`1 -> NULL` and `2 -> 3 -> 4 -> 5 -> NULL`. But no worries because as we continue looping, we're going to rejoin them node by node until the reversed list is complete.

![step by step demonstration of reverse linked list algorithm](https://media.giphy.com/media/d9TdpWRIDu9CXONF8P/giphy.gif)

***
####Some Thoughts
When I finally understood the solution, I felt like my mind was blown. It's really *not* that complicated a problem or a solution, but as the process of the algorithm was drawn out, there became significant shift in my perspective. As I watch the reversal step by step, I realize that all that's being done here is not the rearrangement of the nodes into reverse order, but the *reversal of direction* in the linked list. I've been so focused on the order of nodes, looking at them like in an array, that I wasn't looking at the pointers and the role they played in the data structure. I'd completely overlooked that simply redirecting the pointer could've achieved the same thing. 

![Two identical linked lists going in reverse direction](https://thepracticaldev.s3.amazonaws.com/i/v4326p4rma8x9ktxesry.png)
![Of course](https://media.giphy.com/media/l41YfdYdptDB9RHIA/giphy.gif)

There's really no difference between `NULL <- 1 <- 2 <- 3 <- 4 <- 5` and `5 -> 4 -> 3 -> 2 -> 1 -> NULL`, but for me, seeing the list rotated just 180 degrees changed the way that I perceived linked lists, and I think that it helps me be more flexible in the ways that I approach them in the future. 

I hope these illustrations I created made it easier for you visualize, understand, and replicate this solution to the problem too! 

*** 

*Blog References* 
- [Linked Lists](https://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked%20Lists/linked%20lists.html), Victor S.Adamchik, CMU, 2009
- [How To Reverse A Singly Linked List | The Ultimate Explanation (Iteratively & Recursively)](https://www.youtube.com/watch?v=O0By4Zq0OFc), Benyam Ephrem, Back to Back SWE, 2018
- [Reversing an Integer Mathematically](https://dev.to/jenshaw/reversing-an-integer-mathematically-fmg), Jenny Shaw, dev.to, 2019

*Other Helpful Videos*
- [Introduction to Linked List](https://www.youtube.com/watch?v=WwfhLC16bis&t=383s), CS Dojo
- [Linked Lists](https://www.youtube.com/watch?v=_jQhALI4ujg), Computerphile
- [Singly-Linked Lists](https://www.youtube.com/watch?v=zQI3FyWm144), CS50