Solution: Re-Pointing the Links

We have a correct solution, but it allocates a second list. Now we want to reverse the list by modifying the one we already have, without creating any new items.

Sometimes drawing the structure helps! Let’s say we have the following list:

          ┌───┐     ┌───┐     ┌───┐
head ───▶ │ 3 │ ──▶ │ 5 │ ──▶ │ 7 │ ──▶ null
          └───┘     └───┘     └───┘

Once we reverse it, we want it to look like this:

          ┌───┐     ┌───┐     ┌───┐
newHead ▶ │ 7 │ ──▶ │ 5 │ ──▶ │ 3 │ ──▶ null
          └───┘     └───┘     └───┘

Okay! But wait, let’s keep the boxes and values the same:

          ┌───┐     ┌───┐     ┌───┐
          │ 3 │     │ 5 │     │ 7 │
          └───┘     └───┘     └───┘

The original:

          ┌───┐     ┌───┐     ┌───┐
head ───▶ │ 3 │ ──▶ │ 5 │ ──▶ │ 7 │ ──▶ null
          └───┘     └───┘     └───┘

The reversed:


          ┌───┐     ┌───┐     ┌───┐
 null ◀── │ 3 │ ◀── │ 5 │ ◀── │ 7 │ ◀── newHead
          └───┘     └───┘     └───┘

Now, I am beginning to see a pattern here. The links between the items are reversed! When I visit 3, for example, it currently points to 5, but in the reversed list, 5 points to 3. So if we want to reverse the list in-place, we need to reverse the direction of the links between the items.

But how do we do that? What if I do this when I visit 5? If I keep a reference to the previous item, 3, then I can change 5’s next to point to 3 instead of 7. Here is what I will do: I will maintain three references as I traverse the list: prev, current, and next.

          prev     current    next
            │         │         │
            ▼         ▼         ▼
          ┌───┐     ┌───┐     ┌───┐
head ───▶ │ 3 │ ──▶ │ 5 │ ──▶ │ 7 │ ──▶ null
          └───┘     └───┘     └───┘

At this point, I can do the following:

next = current.next;  // save the next node
current.next = prev;  // reverse the link
prev = current;  // move prev forward
current = next;  // move current forward
// go back to the top of the loop

Let’s put this solution together:

public static ListItem reverseList(ListItem head) {
  ListItem prev = null;
  ListItem current = head;
  ListItem next = null;

  while (current != null) {
    next = current.next;  // save the next node
    current.next = prev;  // reverse the link
    prev = current;  // move prev forward
    current = next;  // move current forward
  }

  return prev;  // at the end, prev will be the new head of the reversed list
}

Two of those choices need an explanation.

We save current.next into next before we do anything else. The reason is the same one we saw with insertAfter. The line current.next = prev overwrites the only reference we have to the rest of the list. If we have not copied it somewhere first, everything after current is unreachable and the traversal cannot continue.

And prev starts at null rather than at head. The first item we visit is the old head, and in the reversed list the old head is the last item, so its next has to end up as null. Starting prev at null does that. It also means the loop body is the same on the first iteration as on every other one, with no special case for the head.

Let’s trace the algorithm on our example list to see how it works! Here is the initial state:

         current
            │
            ▼
          ┌───┐     ┌───┐     ┌───┐
head ───▶ │ 3 │ ──▶ │ 5 │ ──▶ │ 7 │ ──▶ null
          └───┘     └───┘     └───┘

next ───▶ null
prev ───▶ null

After the first iteration of the loop, we have:

                   current
                      │
                      ▼
head ───▶ ┌───┐     ┌───┐     ┌───┐
          │ 3 │     │ 5 │ ──▶ │ 7 │ ──▶ null
null ◀─── └───┘     └───┘     └───┘
            ▲         ▲
            │         │
          prev       next

After the second iteration of the loop, we have:

                             current
                                │
                                ▼
head ───▶ ┌───┐     ┌───┐     ┌───┐
          │ 3 │ ◀── │ 5 │     │ 7 │ ──▶ null
null ◀─── └───┘     └───┘     └───┘
                      ▲         ▲
                      │         │
                     prev      next

After the third iteration of the loop, we have:

                                      current
                                         │
                                         ▼
head ───▶ ┌───┐     ┌───┐     ┌───┐
          │ 3 │ ◀── │ 5 │ ◀── │ 7 │     null
null ◀─── └───┘     └───┘     └───┘
                                ▲        ▲
                                │        │
                              prev      next

Okay, now if you treat prev as the new head of the list, you can see that the list is reversed! The final state of the algorithm is:

          ┌───┐     ┌───┐     ┌───┐
 null ◀── │ 3 │ ◀── │ 5 │ ◀── │ 7 │ ◀── newHead
          └───┘     └───┘     └───┘

Alright! How did we do in terms of time and space complexity?

• The algorithm runs in $O(n)$ time, where $n$ is the number of items in the list, because we visit each item exactly once.
• The auxiliary space complexity is $O(1)$, because we only use a constant amount of extra space for the prev, current, and next references, regardless of the size of the list.