# Reverse a singly linked list

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

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.

`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!