Reverse a Linked List, Java

Reviewing for interview questions, I ran across this. Most solutions you’ll find are in C, and that can be easily adapted … however, the C-ness sometimes gets in the way of spotting the subtleties. Here is the function in Java,

static void Node reverse(Node head) {
Node current = head;
Node newHead = null;
while (current != null) {
Node tmp = current;
current = current.next;
tmp.next = newHead;
newHead = tmp;
}
return newHead;
}

So how does it work? In a nutshell, we always have 2 lists: 1) the remaining portion of the original list pointed to by current, and 2) the new list pointed to by newHead. Each iteration strips the head element from the original list, and adds it to the head of the new list.

• line 5 saves the current loop pointer, this will be our new head at the end of each loop.
• line 6 advances the current loop pointer one past the head, but remember we saved the old current pointer in tmp at line 5.
• line 7 assigns the next pointer of our new head (tmp) to the previous head pointer. The first time through the loop, this is null, and we’ll have a new list containing one item.
• line 8 permanently tracks our new head by moving it out of the temporary loop var.

I can’t imagine it gets better than this. No new allocations, and O(n).