如何高效实现Java LinkedList自定义rotate()元素旋转方法？

因为继承了java.util.LinkedList，我们可以利用它的双向链表特性及内置方法，高效实现符合Unix rotate逻辑的元素旋转功能。

核心逻辑 #

rotate的规则是：传入正整数n时，将列表末尾n个元素移到开头；传入负数-n时，将列表开头n个元素移到末尾。同时需要处理边界情况，比如空列表、旋转0位、旋转次数大于列表长度的场景。

高效实现代码 #

import java.util.LinkedList;
import java.util.Collection;

public class RotatingList<E> extends LinkedList<E> {

    public RotatingList() {
        super();
    }

    public RotatingList(Collection<? extends E> c) {
        super(c);
    }

    public void rotate(int positions) {
        // 空列表或旋转0位直接返回
        if (isEmpty() || positions == 0) {
            return;
        }

        int size = size();
        // 取模简化旋转次数，避免重复循环
        positions = positions % size;
        // 处理负数旋转，转为等价的正数操作
        if (positions < 0) {
            positions += size;
        }

        // 将末尾positions个元素移到开头
        addAll(0, subList(size - positions, size));
        // 删除原末尾的positions个元素
        subList(size - positions, size).clear();
    }
}

代码说明 #

• 边界处理：空列表或旋转0位时直接返回，避免无效操作。
• 模运算优化：当旋转次数大于列表长度时，取模得到等价的最小旋转次数，比如列表长度为5，rotate(7)等价于rotate(2)。
• 负数兼容：负数旋转（如rotate(-2)）等价于将开头2个元素移到末尾，通过positions += size转为正数逻辑，统一处理流程。
• 高效操作：LinkedList的subList是原列表的视图而非拷贝，因此addAll和clear操作均为O(n)时间复杂度，比逐个移动元素效率更高。

测试验证 #

用你给出的示例测试：

public static void main(String[] args) {
    RotatingList<Integer> list = new RotatingList<>(List.of(1, 2, 3, 4, 5));
    list.rotate(2);
    System.out.println(list); // 输出: [4, 5, 1, 2, 3]
    
    // 测试负数旋转场景
    list.rotate(-3);
    System.out.println(list); // 输出: [2, 3, 4, 5, 1]
}

内容的提问来源于stack exchange，提问作者Nepriatel