How to reverse a Singly Linked List
Ricardo Borges
Posted on July 16, 2021
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:
- next point to its next node
- current.next points to previous node
- previous node points to the current node
- 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;
}
A single iteration works like this:
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();
Posted on July 16, 2021
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.