## DEV Community is a community of 783,060 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Mihai Bojin

Posted on • Originally published at mihaibojin.com on

# 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.

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 tail;

// 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) {
}

}

/**
* 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() {
}

/**
* Iterate over elements until none are left
*/
private class LinkedListIterator implements Iterator<T> {

@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()) {
}

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;

@Test
// ARRANGE
List<Integer> input = List.of(1, 2, 3);

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

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

@Test
// ARRANGE

// 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> {
// ...

// initialize references
Node newTail = null;

// while there are elements we haven't seen in the original list
// keep a reference to the next element in the original list

// change the direction of the elements

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

}

// construct the resulting linked list object
result.tail = newTail;
return result;
}
}
``````

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

``````class LinkedListTest {
// ...

@Test
// ARRANGE
List<Integer> input = List.of(1, 2, 3);

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!