29
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.
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.
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()));
}
}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!
29