Reversing a Linked List

A Linked List Problem

I'm learning about Linked Lists 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? 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 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:

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.

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.

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.

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.

Good thing we were prepared and kept that node secured in temp!

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.

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.

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.

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, Victor S.Adamchik, CMU, 2009
• How To Reverse A Singly Linked List | The Ultimate Explanation (Iteratively & Recursively), Benyam Ephrem, Back to Back SWE, 2018
• Reversing an Integer Mathematically, Jenny Shaw, dev.to, 2019

Other Helpful Videos

• Introduction to Linked List, CS Dojo
• Linked Lists, Computerphile
• Singly-Linked Lists, CS50