# Reverse a sublist of a singly-linked master list in constant space and maximum of one pass (Java)

So I found this funky programming challenge somewhere on Quora. The idea is to take the head of a singly-linked list, and reverse a specific sublist. The requirements are:

1. runs in constant space,
2. makes only one pass over the master list.

After hours of hard work, I came with the following solution:

com.quora.algo.list.ReverseLinkedList.java:

package com.quora.algo.list;

import java.util.ArrayDeque;
import java.util.Deque;

/**
* This class provides methods for reversing sublists in singly-linked lists.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Jan 15, 2022)
*/

/**
* Reverses the sublist {@code [fromIndex, toIndex]} in a single pass over
* the singly-linked master list. Runs in {@code O(toIndex)} time. Indices
* start from 1, not 0.
*
* @param fromIndex the index of the leftmost node of the target sublist.
* @param toIndex   the index of the rightmost node of the target sublist.
* @return the head of the resulting list. (May change, if {@code fromIndex}
* is 1.)
*/
public static Node reverse(Node head, int fromIndex, int toIndex) {
return null;
}

checkIndices(fromIndex, toIndex);

// Easy case. Nothing to reverse:
if (fromIndex == toIndex) {
}

Node prefixTail,
sublistPtr,
sublistTail             = null,
previouslyProcessedNode = null;

if (fromIndex == 1) {
prefixTail = null;
} else {

// Go to the fromIndex'th node:
for (int i = 1; i <= fromIndex - 2; ++i) {
if (prefixTail == null) {
throw new IllegalArgumentException(
"fromIndex(" + fromIndex +
") is too large. Must be at most " + (i + 1) + ".");
}

prefixTail = prefixTail.next;
}
}

int numberOfNodesToProcess = toIndex - fromIndex + 2;

// March through the nodes comprising the sublist to reverse. Also, we
// need to find the suffix head node in order to link the tail of the
// reversed sublist to the suffix head:
for (int i = 0; i < numberOfNodesToProcess; ++i) {
Node nodeToProcess = sublistPtr;

if (nodeToProcess == null) {
if (i == numberOfNodesToProcess - 1) {
// Once here, the toIndex points to the tail node of the
// entire list:
} else {
// Oops! toIndex is too large:
throw new IllegalArgumentException(
"toIndex is too large: " + toIndex +
". Must be at most " + (i + 1) + ".");
}
} else if (i < numberOfNodesToProcess - 1) {
sublistPtr = sublistPtr.next;
sublistTail = nodeToProcess;
nodeToProcess.next = previouslyProcessedNode;
}

previouslyProcessedNode = nodeToProcess;
}

if (prefixTail == null) {
return sublistTail;
} else {
prefixTail.next = sublistTail;
}
}

public static void main(String[] args) {
Node tail = null;

int m = Integer.valueOf(args[0]);
int n = Integer.valueOf(args[1]);

for (int i = 2; i < args.length; i++) {
int value = Integer.valueOf(args[i]);

head = tail = new Node(value, null);
} else {
tail = (tail.next = new Node(value, null));
}
}

for (Node node = head; node != null; node = node.next) {
System.out.print(node.value + " ");
}

System.out.println();
}

public static Node safeReverse(Node head, int fromIndex, int toIndex) {
checkIndices(fromIndex, toIndex);

// Easy case. Nothing to reverse:
if (fromIndex == toIndex) {
}

Pair<Node> sublistNodePair = getSublist(head, fromIndex, toIndex);
Node prefixTail = getPrefixTail(head, fromIndex - 1);

if (prefixTail == null) {
return sublistNodePair.second;
}

prefixTail.next = sublistNodePair.second;
}

private static void reverseRelink(Pair<Node> sublist) {
Deque<Node> stack = new ArrayDeque<>();

for (Node node = sublist.first;
node != sublist.second.next;
node = node.next) {

}

Node previousNode = stack.removeFirst();

while (!stack.isEmpty()) {
Node node = stack.removeFirst();
node.next = previousNode;
previousNode = node;
}
}

private static Node getPrefixTail(Node head, int fromIndex) {
if (fromIndex == 0) {
return null;
}

for (int i = 1; i < fromIndex; ++i) {
node = node.next;
}

return node;
}

for (int i = 1; i < toIndex; ++i) {
node = node.next;
}

return node;
}

public static final class Pair<T> {
public final T first;
public final T second;

public Pair(T first, T second) {
this.first = first;
this.second = second;
}
}

int fromIndex,
int toIndex) {
Node start = null, end = null;
int counter = 0;

for (Node node = head; node != null; node = node.next) {
++counter;

if (counter == fromIndex) {
start = node;
} else if (counter == toIndex) {
end = node;
return new Pair<>(start, end);
}
}

}

public static void checkContainsNoCycles(Node head) {

while (ptr1 != null && ptr2 != null) {
ptr1 = ptr1.next;
ptr2 = ptr2.next;

if (ptr2 != null && ptr2.next != null) {
ptr2 = ptr2.next;
}

if (ptr1 == ptr2) {
throw new IllegalStateException(
"The input list contains a cycle!");
}
}
}

private static void checkIndices(int fromIndex, int toIndex) {
if (fromIndex < 1 || toIndex < 1 || fromIndex > toIndex) {
throw new IllegalArgumentException(
"fromIndex(" + fromIndex + "), toIndex(" + toIndex + ")");
}
}
}


com.quora.algo.list.Node.java:

package com.quora.algo.list;

public final class Node {

public final int value;
public Node next;

public Node(int value, Node next) {
this.value = value;
this.next = next;
}

// For debugging:
@Override
public String toString() {
return "[" + value + "]";
}
}


com.quora.algo.list.ReverseLinkedListTest.java:

package com.quora.algo.list;

import static com.quora.algo.list.TestUtils.createList;
import static com.quora.algo.list.TestUtils.eq;
import static com.quora.algo.list.TestUtils.getList;
import java.util.Random;
import static org.junit.Assert.assertTrue;
import org.junit.Before;
import org.junit.Test;

private static final int BRUTE_FORCE_ITERATIONS = 100;

private static Node list1;
private static Node list2;
private static Node list3;
private static Node list4;
private static Node list5;

@Before
public void before() {
list1 = getList(1);
list2 = getList(2);
list3 = getList(3);
list4 = getList(4);
list5 = getList(5);
}

@Test(expected = IllegalArgumentException.class)
public void throwsOnTooSmallFromIndex() {
}

@Test(expected = IllegalArgumentException.class)
public void throwsOnIndicesBackwards() {
}

@Test(expected = IllegalArgumentException.class)
public void throwsOnTooLargeToIndex() {
}

@Test
public void list1TrivialReverse() {
}

@Test
public void listAll2() {
Node result = ReverseLinkedList.reverse(list2, 1, 2);
Node expected = createList(2, 1);

assertTrue(eq(result, expected));
}

@Test
public void listAll3() {
Node result = ReverseLinkedList.reverse(list3, 1, 3);
Node expected = createList(3, 2, 1);

assertTrue(eq(result, expected));
}

@Test
public void bruteForceComparisonTest() {
Random random = new Random(123L);

for (int iteration = 0;
iteration < BRUTE_FORCE_ITERATIONS;
iteration++) {
int length = random.nextInt(10) + 1;
int index1 = random.nextInt(length) + 1;
int index2 = random.nextInt(length) + 1;

int fromIndex = Math.min(index1, index2);
int toIndex = Math.max(index1, index2);

}
}
}


com.quora.algo.list.SafeReverseLinkedListTest.java:

package com.quora.algo.list;

import static com.quora.algo.list.TestUtils.createList;
import static com.quora.algo.list.TestUtils.eq;
import static com.quora.algo.list.TestUtils.getList;
import static org.junit.Assert.assertTrue;
import org.junit.Before;
import org.junit.Test;

private Node list1;
private Node list2;
private Node list3;
private Node list4;
private Node list5;

@Before
public void before() {
list1 = getList(1);
list2 = getList(2);
list3 = getList(3);
list4 = getList(4);
list5 = getList(5);
}

@Test(expected = IllegalArgumentException.class)
public void throwsOnTooSmallFromIndex() {
}

@Test(expected = IllegalArgumentException.class)
public void throwsOnIndicesBackwards() {
}

@Test(expected = IllegalArgumentException.class)
public void throwsOnTooLargeToIndex() {
}

@Test
public void list1TrivialReverse() {
}

@Test
public void listAll2() {
Node result = ReverseLinkedList.safeReverse(list2, 1, 2);
Node expected = createList(2, 1);

assertTrue(eq(result, expected));
}

@Test
public void listAll3() {
Node result = ReverseLinkedList.safeReverse(list3, 1, 3);
Node expected = createList(3, 2, 1);

assertTrue(eq(result, expected));
}
}


com.quora.algo.list.TestUtils.java:

package com.quora.algo.list;

import static com.quora.algo.list.TestUtils.createList;
import static com.quora.algo.list.TestUtils.eq;
import static com.quora.algo.list.TestUtils.getList;
import static org.junit.Assert.assertTrue;
import org.junit.Before;
import org.junit.Test;

private Node list1;
private Node list2;
private Node list3;
private Node list4;
private Node list5;

@Before
public void before() {
list1 = getList(1);
list2 = getList(2);
list3 = getList(3);
list4 = getList(4);
list5 = getList(5);
}

@Test(expected = IllegalArgumentException.class)
public void throwsOnTooSmallFromIndex() {
}

@Test(expected = IllegalArgumentException.class)
public void throwsOnIndicesBackwards() {
}

@Test(expected = IllegalArgumentException.class)
public void throwsOnTooLargeToIndex() {
}

@Test
public void list1TrivialReverse() {
}

@Test
public void listAll2() {
Node result = ReverseLinkedList.safeReverse(list2, 1, 2);
Node expected = createList(2, 1);

assertTrue(eq(result, expected));
}

@Test
public void listAll3() {
Node result = ReverseLinkedList.safeReverse(list3, 1, 3);
Node expected = createList(3, 2, 1);

assertTrue(eq(result, expected));
}
}


(pom.xml is here.).

Critique request

Please, tell me anything that comes to mind.

PS: safeReverse is there for comparing the actual method to something that can be easily deemed correct.

• (ReverseLinkedList.main() & checkContainsNoCycles() look derelict.) Commented Jan 15, 2022 at 13:30
• I think in real world I would rather inverse the whole list, and for reversing a sublist I'd make a separate function to split a list into up to 3 segments, reverse the middle part and then concatenate them back. That makes the code much simpler, although it's against the one-pass requirement. Commented Jan 16, 2022 at 11:49
• @CiaPan That's exactly what ReverseLinkedList.safeReverse does. Commented Jan 16, 2022 at 13:20

With a class containing static methods, only (like ReverseLinkedList), I can see final as a hint to keep it that way. (Make it abstract to block instantiation and support the notion.)

But why make Node a class? A final one, at that?
• Program to interfaces/specifications, not implementations.
Especially given multiple inheritance with interfaces, but not classes.

(public static void checkContainsNoCycles(Node head) lacks a doc comment.

Appreciating the presence of tests, focusing ReverseLinkedList() from here.)

(Late) Idea how Node reverse(head, fromIndex, toInclusive) got to its present(ed) state:

1. specification
2. top-down design (&implementation?) of Node safeReverse(head, fromIndex, toInclusive)
3. coding

I find the naming helpful, I think you were explicitly trying to have it document your code.
Consider making some of the variables final.

Handling off-the-end indices in two places lead to a copy&paste error:
The message about toIndex is true only when fromIndex == 1.

Somehow, all those variable seem to have complicated things.
Not copying the doc comment to highlight a problem I see with Java's doc comments avoided in Python docstrings:

    /** @throws <code>IllegalArgumentException}</code>
*              if {@code fromIndex} < 1 or {@code toInclusive < fromIndex}
*  @return {@code fromIndex == toInclusive} (reverse idempotent)
*/
private static boolean nonMutating(int fromIndex, int toInclusive) {
if (0 < fromIndex && fromIndex <= toInclusive) {
return fromIndex == toInclusive;
}
throw new IllegalArgumentException(
"fromIndex(" + fromIndex + "), toIndex(" + toInclusive + ")");
}

public static Node reverse(Node head, int fromIndex, final int toInclusive) {
if (head == null || nonMutating(fromIndex, toInclusive)) {
}

final Node
prefixTail,     // known to stay unreversed
Node
node = head,    // iterating the list
int i = 1;          // like node outside try for message in catch
try {
// Go to the fromIndex'th node:
while (++i < fromIndex) {
node = node.next;
}
prefixTail = node;
node = headTurnsTail = prefixTail.next; // may throw NPE

// March through the nodes comprising the sublist to reverse.
for (/*i = fromIndex*/ ; i <= toInclusive ; i++) {
Node nextNode = node.next;
node.next = reversed;
reversed = node;
node = nextNode;
}
} catch (NullPointerException npe) {
throw new IllegalArgumentException(
(i < fromIndex ? ("fromIndex(" + fromIndex):
"toIndex(" + toInclusive)
+ ") is too large: Must be at most " + i + ".", npe);
}
prefixTail.next = reversed;