Reverse Linked List

Let’s practice reversing a singly linked list as this is a popular interview question!

The problem is, given the head of a singly linked list, reverse it, and return the reversed list.

We can solve this problem by reordering the original list instead of creating a new one, and returning the tail node as the new head of the list.

If we’ll look at the first node, what do we know about it? We know that it has a pointer to the next node, and no nodes pointing to it. If we reverse its next pointer backwards immediately, we’ll orphan the rest of the list. In addition, we don't know which node should it point to. We need some helper cursors to keep track of the nodes!

Thus, we will define three cursors: curr to remember the current node, prev to remember its previous node (firstly initialized to null), and tmp to remember the next node (we’ll define it as a local variable inside the loop).

const reverseList = (head) => {
  let curr = head; //cursor to the current node
  let prev = null; //cursor to the previous node
...
}

Since we remember the next node, we can safely change the cursors. But the order is important!

First, we move our curr pointer backwards to link it with the previous node (or null initially):

curr.next = prev;

Then prev becomes our current node, and the current becomes the next node:

prev = curr;
curr = tmp;

That’s it, in the next iteration we can move to the next node and repeat the process.

We keep moving along the list unless we reach the end (the current cursor points to null). By the end of the cycle, we return a new head of the list, our prev node (not prev.next since prev.next is null).

while (curr) { //curr !== null
    let tmp = curr.next; //move cursor to the next node

    curr.next = prev; //1.change curr pointer backwards
    prev = curr; //2.change prev cursor to current
    curr = tmp; //3.move cur cursor to the next node
  }

Let's put it all together.

const reverseList = (head) => {
  let curr = head; //cursor to the current node
  let prev = null; //cursor to the previous node

  while (curr) { //curr !== null
    let tmp = curr.next; //move cursor to the next node

    curr.next = prev; //1.change curr pointer backwards
    prev = curr; //2.change prev cursor to current
    curr = tmp; //3.move cur cursor to the next node
  }
  return prev; //return a new head of the list
};

We can do it better with recursion! Know how? Please feel free to share your solution in the comments!