Problem: Reverse a Linked List

Let’s look at a classic problem: reversing a linked list.

A common constraint for this problem is that the reversal must be done in place, with $O(1)$ auxiliary space. We cannot build another list or array to hold the reversed elements. We have to reverse the list by changing the links in the nodes we already have.

The signature of the method in Java might look like this:

public static ListItem reverseList(ListItem head) {
  // Your implementation goes here
}

Here ListItem is the class we defined earlier in this chapter.

You will be given the head of a linked list. If you traverse it, you get, for example, head → 7 → 3 → 5 → null. The method should change the links and return the new head. So if the caller writes:

head = reverseList(head);

then traversing from head would give head → 5 → 3 → 7 → null.

There are two special cases to think about:

• If the input list is empty, that is, head is null, the method should return null.
• If the list has only one node, the reversed list is the same as the original list, so the method should return the same head.

I suggest that you start by solving this problem without the in-place constraint. That will let you work out how to reverse the list. Then modify your solution so that it does not use the extra space.