Category: Angry Algorithms

I previously made a post with some shittily drawn diagrams, trying to make sense of how linked list reversal works in JavaScript.

However, some of my diagrams were slightly inaccurate on second look, and also, for me, in order to visualise something like this properly it helps me to see it in motion.

To that end I’ve coded up a new solution, inspired by this video:

https://www.youtube.com/watch?time_continue=119&v=O0By4Zq0OFc&feature=emb_title

and filmed a shaky video in order to animate my terrible drawings. This is the code for the linked list, complete with reversal method:

class LinkedList {
  constructor(val) {
    this.head = {
      value: val,
      next: null,
    };
    this.tail = this.head;
  }

  append(val) {
    this.tail.next = {
      value: val,
      next: null,
    };
    this.tail = this.tail.next;
  }

  print() {
    const displayArray = [];
    let node = this.head;
    while (node) {
      displayArray.push(node.value);
      node = node.next;
    }
    console.log(displayArray);
  }

  reverse() {
    let current = this.head;
    let previous = null;
    let next = null;

    while (current) {
      next = current.next;
      current.next = previous;
      previous = current;
      current = next;
    }

    this.head = previous;
  }
}

const list = new LinkedList(1);
list.append(2);
list.append(3);
list.print();

list.reverse();
list.print();

And here is the reverse method visualised with the magic of video (I would watch at 2X speed if you value your time in any way):

sweet sweet animation video

Also, if you really want to figure out how this code works, I highly recommend making your own cut outs and moving them around. Beats staring at a screen.

This is one of those algorithms questions that makes my stomach hurt.

If you haven’t seen this before prepare to put your brain through a blender.

How do you reverse a linked list in JavaScript?

Firstly, you have to have a linked list. Luckily I have one I prepared earlier. JavaScript doesn’t have a linked list implementation, so we have to make our own:

class LinkedList {
  constructor(val) {
    this.head = {
      value: val,
      next: null,
    };
    this.tail = this.head;
  }

  append(val) {
    this.tail.next = {
      value: val,
      next: null,
    };
    this.tail = this.tail.next;
  }

  print() {
    const displayArray = [];
    let node = this.head;
    while (node) {
      displayArray.push(node.value);
      node = node.next;
    }
    console.log(displayArray);
  }
}

const list = new LinkedList(1);
list.append(2);
list.append(3);
list.append(4);
list.append(5);

list.print();

When this is run it will print [1,2,3,4,5], which under the hood looks like 1=>2=>3=>4=>5, with a reference to the start (head), and the end (tail) of the chain, or snake, or whatever we decide we want to think of our list as.

We can easily get to the first element, and we can easily get to the last element.

Cooooool. Now reverse it, turn those arrows the other way.

My first attempt at this worked quite nicely, but is wasteful with memory (a sin in computer science). Here it is:

  reverse() {
    const buffer = [];

    let node = this.head;

    while(node) {
      buffer.push(node.value);
      node = node.next;
    }

    this.head = {
      value: buffer.pop(),
      next: null,
    };

    node = this.head;

    while(buffer.length) {
      node.next = {
        value: buffer.pop(),
        next: null,
      }
      node = node.next;
    }
  }
}

So just stick all the values from the linked list into an array, then pull items off the array and rewrite our linked list from scratch!

I know, I’m a genius.

The runtime is O(n), which is good.

The space complexity is also O(n), which is less good. At this point if you are interviewing, I imagine the interviewer (if they even let you code this basic solution), will be tutting and saying things like ‘but can we do better?’, scratching their chin and gesticulating with whiteboard markers.

And it turns out that yes, there is a better solution. The bad news is that it is utterly brain melting to actually understand. If you get what this is doing straight off the bat, all power to you.

    reverse() {
      let first = this.head;
      this.tail = this.head;
      let second = first.next;

      while(second) {
        const temp = second.next;
        second.next = first;
        first = second;
        second = temp;
      }

      this.head.next = null;
      this.head = first;
    }

In my case it just made me want to cry and shout and stomp my feet and yell ‘BUT WHY DO I HAVE TO DO THIS STUPID SHIT. I’M A FRONTEND DEVELOPER, LET ME DO SOME CSS OR SOMETHING. I’LL JUST GOOGLE IT. THIS IS BULLSHIT!!!?!!’.

Obviously, we are onto a good problem. The ones that expand your brain and make you better at problem solving normally start with this sort of reaction. The key to getting gud is to gently soothe and comfort your troubled brain, and trust that given enough sustained concentration on the problem, some youtube videos, and a bit of sleep, this will start to make sense.

Let’s draw some pictures and match them to code (DISCLAIMER: These diagrams are not totally accurate… I’ve left them now though as this is useful as a record for me of how my thinking progressed. For a better illustration of how this algorithm works, see this post) :

We’re going to use a smaller list for this run through, because I can’t be arsed to draw endless diagrams.

We want to turn 1=>2=>3 into 3=>2=>1.

What

a time

to be alive.

let first = this.head;
this.tail = this.head;
let second = first.next;

Just assigning things for now, seems OK. See brain, nothing to be scared about. Right?

‘THIS IS BULLSHIT. WHAT THE FUCK ARE WE EVEN BOTHERING WITH THIS FOR. LET’S PLAY ROCKET LEAGUE’

Our diagram is in this state now:

OK. Next bit.

      while(second) {
        const temp = second.next;
        second.next = first;
        first = second;
        second = temp;
      }

…

…

…

This appears to be a loop. Let’s try one iteration first, and update our diagram.

second is pointing to the element with the value 2 for us currently, so it is truthy. We enter the while loop, filled with trepidation.

const temp = second.next

second.next = first

first = second

second = temp

Oooh wow, this kind of looks like progress, we swapped 2 and 1, and our variables are all pointing at sensible looking things. Apart from second, which is not pointing at the second element, and head which is just floating in the middle of the list. I think this is one of the tricky parts of linked list questions, the variable names end up not making sense mid way through the problem.

Let’s continue.

second is pointing to the element with the value 3, so it is truthy. We enter the while loop again, brimming with new found confidence.

const temp = second.next

temp gets set to second.next, which is now null.

second.next = first

first = second

second = temp

Second is null now, so we avoid the while loop this time round.

this.head.next = null

So we sever that endless loop setting head.next to null

this.head = first

We’ve set up our newly ordered linked list, now we just need to make it official by updating the head reference.

this.head = first;

Anddddd done.

I’m going to need to revisit this, but this scribbling exercise has already helped. I hope it helps you too.

Alternatively, go watch this video https://www.youtube.com/watch?time_continue=119&v=O0By4Zq0OFc&feature=emb_title as it explains the approach waaaaay better than these scribbles do. Wish I’d watched that first…