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

Question

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)
 */
public final class ReverseLinkedList {

    /**
     * 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 head      the head node of the list.
     * @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) {
        if (head == null) {
            return null;
        }
        
        checkIndices(fromIndex, toIndex);
        
        // Easy case. Nothing to reverse:
        if (fromIndex == toIndex) {
            return head;
        }
        
        Node prefixTail,
             sublistPtr,
             sublistHead,
             sublistTail             = null,
             suffixHead              = null,
             previouslyProcessedNode = null;
        
        if (fromIndex == 1) {
            prefixTail = null;
            sublistHead = head;
        } else {
            prefixTail = head;
            sublistHead = head.next;
            
            // 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;
                sublistHead = sublistHead.next;
            }
        }
        
        sublistPtr = prefixTail == null ? head : sublistHead;
        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:
                    suffixHead = null;
                } 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) {
                // Relink:
                sublistPtr = sublistPtr.next;
                suffixHead = sublistPtr;
                sublistTail = nodeToProcess;
                nodeToProcess.next = previouslyProcessedNode;
            }
            
            previouslyProcessedNode = nodeToProcess;
        }
        
        if (prefixTail == null) {
            sublistHead.next = suffixHead;
            return sublistTail;
        } else {
            prefixTail.next = sublistTail;
            sublistHead.next = suffixHead;
            return head;
        }
    }
    
    public static void main(String[] args) {
        Node head = null;
        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]);
            
            if (head == null) {
                head = tail = new Node(value, null);
            } else {
                tail = (tail.next = new Node(value, null));
            }
        }
        
        head = reverse(head, m, n);
        
        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) {
            return head;
        }
        
        Pair<Node> sublistNodePair = getSublist(head, fromIndex, toIndex);
        Node prefixTail = getPrefixTail(head, fromIndex - 1);
        Node suffixHead = getSuffixHead(head, toIndex + 1);
        
        reverseRelink(sublistNodePair);
        sublistNodePair.first.next = suffixHead;
        
        if (prefixTail == null) {
            return sublistNodePair.second;
        }
        
        prefixTail.next = sublistNodePair.second;
        return head;
    }
    
    private static void reverseRelink(Pair<Node> sublist) {
        Deque<Node> stack = new ArrayDeque<>();
        
        for (Node node = sublist.first; 
             node != sublist.second.next; 
             node = node.next) {
            
            stack.addLast(node);
        }
        
        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;
        }
        
        Node node = head;
        
        for (int i = 1; i < fromIndex; ++i) {
            node = node.next;
        }
        
        return node;
    }
    
    private static Node getSuffixHead(Node head, int toIndex) {
        Node node = head;
        
        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;
        }
    }
    
    private static Pair<Node> getSublist(Node head, 
                                         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);
            }
        }
        
        throw new IllegalArgumentException("Bad indices!");
    }
    
    public static void checkContainsNoCycles(Node head) {
        Node ptr1 = head;
        Node ptr2 = 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;

public class ReverseLinkedListTest {
    
    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() {
        ReverseLinkedList.reverse(list1, 0, 1);
    }
    
    @Test(expected = IllegalArgumentException.class) 
    public void throwsOnIndicesBackwards() {
        ReverseLinkedList.reverse(list2, 2, 1);
    }
    
    @Test(expected = IllegalArgumentException.class)
    public void throwsOnTooLargeToIndex() {
        ReverseLinkedList.reverse(list5, 2, 6);
    }
    
    @Test
    public void list1TrivialReverse() {
        ReverseLinkedList.reverse(list1, 1, 1);
    }
    
    @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;
            Node head1 = getList(length);
            Node head2 = getList(length);
            int index1 = random.nextInt(length) + 1;
            int index2 = random.nextInt(length) + 1;
            
            int fromIndex = Math.min(index1, index2);
            int toIndex = Math.max(index1, index2);
            
            head1 = ReverseLinkedList.reverse(head1, fromIndex, toIndex);
            head2 = ReverseLinkedList.safeReverse(head2, fromIndex, toIndex);
            
            assertTrue(eq(head1, head2));
        }
    }
}

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;

public class SafeReverseLinkedListTest {
    
    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() {
        ReverseLinkedList.safeReverse(list1, 0, 1);
    }
    
    @Test(expected = IllegalArgumentException.class) 
    public void throwsOnIndicesBackwards() {
        ReverseLinkedList.safeReverse(list2, 2, 1);
    }
    
    @Test(expected = IllegalArgumentException.class)
    public void throwsOnTooLargeToIndex() {
        ReverseLinkedList.safeReverse(list5, 2, 6);
    }
    
    @Test
    public void list1TrivialReverse() {
        ReverseLinkedList.safeReverse(list1, 1, 1);
    }
    
    @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;

public class SafeReverseLinkedListTest {
    
    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() {
        ReverseLinkedList.safeReverse(list1, 0, 1);
    }
    
    @Test(expected = IllegalArgumentException.class) 
    public void throwsOnIndicesBackwards() {
        ReverseLinkedList.safeReverse(list2, 2, 1);
    }
    
    @Test(expected = IllegalArgumentException.class)
    public void throwsOnTooLargeToIndex() {
        ReverseLinkedList.safeReverse(list5, 2, 6);
    }
    
    @Test
    public void list1TrivialReverse() {
        ReverseLinkedList.safeReverse(list1, 1, 1);
    }
    
    @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.

Answer 1

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)) {
            return head;
        }
        
        final Node
            preHead = new Node(-42, head),
            prefixTail,     // known to stay unreversed
            headTurnsTail;  // sublist head before, tail after reversal
        Node
            node = head,    // iterating the list
            reversed = null;// already reversed
        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;
        headTurnsTail.next = node;
        return preHead.next;
    }