Solution: Building a New List

We are given the head of a singly linked list, and we want to reverse the list and return the new head. For now, let’s ignore the in-place requirement and just focus on getting a correct solution.

I think a good starting point is to simply set up the loop that traverses the list, and then we will figure out how to reverse it.

So reusing our traversal code, we can write:

public static ListItem reverseList(ListItem head) {
  ListItem current = head;
  while (current != null) {
    // we'll fill this in later
    current = current.next;
  }
  return head;  // we'll change this later too
}

Now we have a loop that traverses the list, so we get to visit each item. My first thought is to just create an array to hold the values as we traverse, and then loop through the array in reverse to build a new list.

public static ListItem reverseList(ListItem head) {
  int[] values = new int[?];  // we need to figure out the size of the list first

  ListItem current = head;
  while (current != null) {
    // we'll fill this in later
    current = current.next;
  }
  return head;  // we'll change this later too
}

We need to know how many items are in the list to create the array, and we do not have that number upfront. If we want to continue with this approach, we have a couple of options:

• We could do a first pass to count the items, then create the array, then do a second pass to fill it.

• We could use the DynamicArray we built earlier to hold the values as we traverse, since it grows on its own.

I have already relaxed the constraint about extra space, so either option is allowed. But both of them are a fair amount of code for what we are trying to do.

With a linked list, we can build the list as we go. We do not have to know the size upfront, and we do not have to resize anything the way we would with an array.

So instead of using an array to hold the values, we can just build the reversed list as we traverse the original list.

Let’s for a moment forget we are dealing with a linked list, and just think about the problem of reversing a sequence of values. Imagine I was reading you a list of numbers, and I wanted you to store them in a linked list, in the order I read them. That is not hard. We can do something like this:

• Put the first number in the head of the list.
• For each subsequent number, call addLast to append it to the end of the list.

Now, if I wanted to reverse the order of the numbers, you could just call addFirst instead of addLast for each number after the first. That way, each new number would be added to the front of the list, so the previous numbers come after it. This would in fact be a more efficient way of building up a linked list when you only have access to its head, because addFirst is $O(1)$ while addLast is $O(n)$.

So the process of reversing a sequence is essentially the same as building a new list by prepending each new item instead of appending it.

Let’s apply this idea to our problem:

private static ListItem addFirst(ListItem head, int value) {
  ListItem newItem = new ListItem(value);
  newItem.next = head;
  return newItem;
}

public static ListItem reverseList(ListItem head) {
  ListItem reversedHead = null;
  ListItem current = head;
  while (current != null) {
    reversedHead = addFirst(reversedHead, current.value);
    current = current.next;
  }
  return reversedHead;
}

This code solves the problem correctly. It is $O(n)$ in time: we traverse the original list once, and each addFirst does a constant amount of work, so the loop does $n$ steps of constant work. It is $O(n)$ in space, because we allocate one new ListItem for every item in the original list.

That space is the problem. The requirement was to reverse the list in place, and this solution builds a second list of the same size instead. The original list is left exactly as it was, and we return the head of a new list.

Prepending each value as we traverse forward gives us the reversed order. In the next section we keep that idea, but without allocating new items.