Reversing a Singly Linked List

A linked list is essentially a collection of nodes which each contain a data field and a reference (or link/pointer) to the next node within the list.

Think of a larger theater on Broadway where you ask an usher for help to find your seats. The usher will tell you where to go… and then you will find another usher who might tell you to go see yet another usher! (If the theater is big enough, that is)

Reversing a linked list is a common interview problem that is used to gauge a programmer’s understanding of data structures and algorithms.

I figured I’d share some Javascript code to show how to reverse a linked, along with a class that is used to instantiate nodes that point to one another.

//First - create a class that will allow us to create node elements by passing in a value and a pointer to the next node
const node = class {
  constructor(value, next) {
    this.value = value;
    this.next = next;
  }
};

//Second - Create several nodes to create a singly linked list
let node1 = new node("First node", null); //this is the TAIL of the linked list since its next property is set to null
let node2 = new node("second node", node1);
let node3 = new node("Third node", node2);
let node4 = new node("Fourth node", node3); //this is the HEAD of the linked list

console.log("\x1b[33m%s\x1b[0m", "Linked list before reversal:");
console.log(node4);

//Create a function that we can invoke to reverse a singly linked list
function reverse(head) {
  let node = head;
  let previous, tmp; //these will be placeholder values so we never lose track of what the next node is

  while (node) {
    // save next before we overwrite node.next!
    tmp = node.next;

    // reverse pointer
    node.next = previous;

    // step forward in the list
    previous = node;
    node = tmp;
  }
  //the reversed linked list is stored within the previous variable - don't forget to return it!
  return previous;
}

console.log("\x1b[33m%s\x1b[0m", "Linked list after reversal:");
console.log(reverse(node4));

Hopefully the comments in the code provided some insight in to what was going on line-by-line. And here is the output logged to the console when you run the above code:

Linked list before reversal:
node {
  value: 'Fourth node',
  next: node {
    value: 'Third node',
    next: node { value: 'second node', next: [node] }
  }
}
Linked list after reversal:
node {
  value: 'First node',
  next: node {
    value: 'second node',
    next: node { value: 'Third node', next: [node] }
  }
}

One nifty thing I’d like to point out: Check out this Stack Overflow post on how to add color to the messages you log out to the console.