How to reverse a Singly Linked List

ricardo_borges

Ricardo Borges

Posted on July 16, 2021

How to reverse a Singly Linked List

In a Singly Linked List, each node has only a pointer to the next node, and there are some ways to reverse it, the one that I want to show here doesn't require extra space.

In this algorithm, we start from the list's head, and we use three pointers, each one for previous node, current node and next node.
In the beginning, The current and the next points to the list's head, and the previous points to null. While the current are pointing to a node we do the following:

  1. next point to its next node
  2. current.next points to previous node
  3. previous node points to the current node
  4. current node points to next node

This loop continues until the current points to null, which will mean that we reached the end of the list. Like this:

prev = null;
current = head;
next = head;

while (current !== null) {
  next = next.next;
  current.next = prev;
  prev = current;
  current = next;
}
Enter fullscreen mode Exit fullscreen mode

A single iteration works like this:

images

This algorithm may vary according to the Linked List implementation, using this implementation, looks like this:

function reverse(linkedList: LinkedList<number>) {
  let prev = null;
  let current = linkedList.head;
  let next = linkedList.head;

  while (current !== null) {
    next = next.next;
    current.next = prev;
    prev = current;
    current = next;
  }

  linkedList.head = prev;
}

const linkedList = new LinkedList((a: number, b: number) => a === b);

linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.append(4);
linkedList.append(5);

reverse(linkedList);

linkedList.traverse();
Enter fullscreen mode Exit fullscreen mode
💖 💪 🙅 🚩
ricardo_borges
Ricardo Borges

Posted on July 16, 2021

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related

How to reverse a Singly Linked List
linkedlist How to reverse a Singly Linked List

July 16, 2021

Linked Lists in Swift
programming Linked Lists in Swift

October 5, 2018