HTF do I reverse a linked list (video)

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.

Leave a Reply

Your email address will not be published. Required fields are marked *