A very common interview question is to reverse a linked list without using recursion. If you’ve never done it before, this one can be challenging, especially if you don’t think visually.
The basic idea here is to keep a pointer to
- The previous node so that you don’t lose what you’re going to point the current node’s next pointer at.
- The current node.
- The next node, so that when you point the current node’s next pointer at the previous node, you don’t lose the reference to move on to next.
From there, after pointing the current node’s next pointer to the previous node, you just ‘inchworm’ your way forward until you’ve hit all nodes. At the end repoint the head to be where you’re at.
Here’s some code:
public void reverse() {
if(this.head == null || this.head.next == null) {
return;
}
Node previous = null;
Node current = this.head;
Node next = this.head.next;
while(next != null) {
current.next = previous;
previous = current;
current = next;
next = current.next;
}
current.next = previous;
this.head = current;
}