Rotating lists in linear time and constant space (Java)

Question

(The next iteration.)

I have this small utility method for rotating java.util.Lists in linear time, constant space:

package net.coderodde.util;

import java.util.Arrays;
import java.util.Collections;
import static java.util.Collections.swap;
import java.util.List;
import java.util.Objects;
import java.util.Scanner;

/**
 * This class contains a static method for rotating lists in linear time and
 * constant space.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Oct 6, 2017)
 */
public final class ListReversal {

    private ListReversal() {}

    /**
     * Performs the list rotation.
     * 
     * @param <T>           the list element type.
     * @param list          the list whose content to rotate.
     * @param rotationCount the number of steps to rotate to the right. If
     *                      negative, rotates to the left.
     */
    public static <T> void rotate(List<T> list, int rotationCount) {
        Objects.requireNonNull(list, "The input list is null.");

        if (rotationCount < 0) {
            rotateLeft(list, -rotationCount);
        } else if (rotationCount > 0) {
            rotateRight(list, rotationCount);
        }
    }

    private static <T> void rotateLeft(List<T> list, int rotationCount) {
        Collections.<T>reverse(list);
        rotationCount %= list.size();
        reverse(list, list.size() - rotationCount, list.size());
        reverse(list, 0, list.size() - rotationCount);
    }

    private static <T> void rotateRight(List<T> list, int rotationCount) {
        Collections.<T>reverse(list);
        rotationCount %= list.size();
        reverse(list, 0, rotationCount);
        reverse(list, rotationCount, list.size());
    }

    private static <T> void reverse(List<T> list, int fromIndex, int toIndex) {
        for (int i = fromIndex, j = toIndex - 1; i < j; ++i, --j) {
            swap(list, i, j);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Integer> list = Arrays.asList(1, 2, 3, 4, 5, 6);
        System.out.println(list);

        while (true) {
            int rotationCount = scanner.nextInt();
            rotate(list, rotationCount);
            System.out.println(list);
        }
    }
}

I would like to hear any comments regarding the above.

Answer 1

1. The time complexity of the rotate method is O(N^2) if the list doesn't support random access because each call to swap takes O(N) time. One can fix it by using two ListIterators (one going forward and one going backwards) to reverse a part of the list.

2. There's no need to create separate rotateLeft and rotateRight methods. You can always take the shift modulo the size of the list (in mathematical sense, without negative results, not in a sense of the operator %) instead.