A very common CS problem is to reverse a linked list without using recursion. If you’ve never done it before it can be challenging, especially if you don’t think visually. I found it useful to draw it out on a whiteboard so I could see the algorithm step by step.

The basic idea here is to maintain 3 pointers as you work your way along the list chain.

1. The previous node so that you don’t lose what you’re going to point the current node’s next pointer at.
2. The current node.
3. 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.

At each node along the chain you point the current node’s ‘next’ pointer to the previous node and ‘inchworm’ your way forward until you’ve hit all nodes. At the end repoint the ‘head’ to be where you’re at.

Here is what that might look like in Java. I added comments to help illustrate each step since it can sometimes be hard to map what you see in code to how the algorithm is described abstractly.

class LinkedList {

public void reverse() {

// nothing to do because its an empty list, or a list with 1 element
return;
}

// here are those pointers I talked about above
Node previous = null;

// inchworm through the list until the end
while(next != null) {

// make this one point backwards instead of forwards
current.next = previous;

previous = current;
current = next;
next = current.next;

}

current.next = previous;

// the new head is the former tail