Reverse a singly linked list

🔔 This article was originally posted on my site, MihaiBojin.com. 🔔

Given a reference to the head of a singly linked list, reverse it and return a reference to the head of the reversed list.

This is a simple problem that can be solved in a few ways. In this article, I will solve it in the most elegant way I know - in-place, in linear time.

Note: if you're not familiar with this data structure, see the Wikipedia article on Linked Lists.

A simple LinkedList implementation

But first, let's start with a simple singly linked list implementation.

import java.util.*;

public class LinkedList<T> implements Iterable<T> {
  private Node head;
  private Node tail;

  public void add(T value) {
    if (this.head != null) {
      // the majority use-case: the head element exists
      this.tail.next = new Node(value);
      this.tail = this.tail.next;
      return;
    }

    initFirstElement(value);
  }

  private void initFirstElement(T value) {
    this.head = new Node(value);
    this.tail = head;
  }

  public void addAll(List<T> values) {
    values.forEach(this::add);
  }

  /**
   * A singly linked list node
   */
  private class Node {
    private T value;
    private Node prev = null;
    private Node next = null;

    private Node(T value) {
      this.value = value;
    }
  }
}

The code above represents a very simple linked list implementation that forms the foundation of our problem.

Before we proceed, we can make it a bit nicer. First, we need to retrieve all of the list's elements, in order.

The Java idiomatic way is to implement an Iterator.

public class LinkedList<T> implements Iterable<T> {
  // ...

  @Override
  public Iterator<T> iterator() {
    return new LinkedListIterator();
  }

  /**
   * Iterate over elements until none are left
   */
  private class LinkedListIterator implements Iterator<T> {
    private Node cursor = LinkedList.this.head;

    @Override
    public boolean hasNext() {
      return cursor != null;
    }

    @Override
    public T next() {
      try {
        return cursor.value;
      } finally {
        cursor = cursor.next;
      }
    }
  }
}

Another nicety is to override the toString method so that we can print out the list's elements:

public class LinkedList<T> implements Iterable<T> {
  // ...

  @Override
  public String toString() {
    List<T> results = new ArrayList<>();
    Iterator<T> it = this.iterator();
    while (it.hasNext()) {
      results.add(it.next());
    }

    return results.toString();
  }
}

Of course, before we proceed, let's ensure our custom linked list implementation works as expected.

For the examples below, I used JUnit 5 and Hamcrest, but you can substitute them as you want.

import java.util.List;

import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.Matchers.equalTo;

class LinkedListTest {

  @Test
  void testLinkedListImplementation() {
    // ARRANGE
    List<Integer> input = List.of(1, 2, 3);
    LinkedList<Integer> tested = new LinkedList<>();

    // ACT
    tested.addAll(input);
    String output = tested.toString();

    // ASSERT
    assertThat("Expecting the same elements", output.toString(), equalTo(input.toString()));
  }

  @Test
  void testEmptyLinkedList() {
    // ARRANGE
    LinkedList<Integer> tested = new LinkedList<>();

    // ACT
    String output = tested.toString();

    // ASSERT
    assertThat("Expecting an empty list", output.toString(), equalTo(List.of().toString()));
  }
}

Solving the puzzle

One easy way to solve this problem is to iterate over all the list's elements, add them to a stack, and then pop them. This approach works, but it requires O(N) extra space.

If you'd be trying to reverse a list with millions of elements, you might run out of heap space.

We can do better!

As with most linked list algorithms, you can rely on two cursors:

the first one keeps a reference to the last element in the reversed list

the second one keeps a reference to the new head of the original list

Step by step, we will iterate over the original list, constructing it as we go along. In the end, we will be left with a reference to the head of the reversed list.

Let's see this in action!

public class LinkedList<T> implements Iterable<T> {
  // ...

  public LinkedList<T> reverse() {
    // initialize references
    Node newHead = null;
    Node oldHead = this.head;
    Node newTail = null;

    // while there are elements we haven't seen in the original list
    while (oldHead != null) {
      // keep a reference to the next element in the original list
      Node next = oldHead.next;

      // change the direction of the elements
      oldHead.next = newHead;

      // oldHead becomes newHead (the reversed list's head)
      newHead = oldHead;

      // at this point, keep a reference to the reversed list's new tail
      // we will need it later
      if (newTail == null) {
        newTail = newHead;
      }

      // advance the read element, in the original list
      oldHead = next;
    }

    // construct the resulting linked list object
    LinkedList<T> result = new LinkedList<>();
    result.head = newHead;
    result.tail = newTail;
    return result;
  }
}

Of course, we also need a test to confirm the solution works:

class LinkedListTest {
  // ...

  @Test
  void testReverseLinkedList() {
    // ARRANGE
    List<Integer> input = List.of(1, 2, 3);
    LinkedList<Integer> tested = new LinkedList<>();
    tested.addAll(input);

    List<Integer> expected = List.of(3, 2, 1);

    // ACT
    String output = tested.reverse().toString();

    // ASSERT
    assertThat("Expecting the same elements, in reverse order", output.toString(), equalTo(expected.toString()));
  }
}

And there you have it: in-place (no extra space), linear (iterate over the input only once), singly linked list reversal.

I hope you enjoyed this exercise; it is a more elegant solution than its simpler alternative (using a stack).

Understanding the dual pointer concept is the key to efficiently solving linked list coding puzzles. Therefore, I recommend spending a bit of time studying it, as it will surely come in handy!

If you have any questions or seek any advice, please (DM me on Twitter)!

Until next time...

If you liked this article and want to read more like it, please subscribe to my newsletter; I send one out every few weeks!