DEV Community

Veronika Fatikhova
Veronika Fatikhova

Posted on

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.

Image description


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).

Image description

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

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):

Image description

curr.next = prev;
Enter fullscreen mode Exit fullscreen mode

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

Image description

prev = curr;
curr = tmp;
Enter fullscreen mode Exit fullscreen mode

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

Image description

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).

Image description

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
  }
Enter fullscreen mode Exit fullscreen mode

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
};
Enter fullscreen mode Exit fullscreen mode

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

Top comments (0)