算法题解：旋转链表（Rotate List）

思路一：双指针配合长度计算

由于 k 可能比链表长度大，直接旋转会导致无效操作。我们需要先获取链表长度，然后计算实际需要移动的步数。

基本逻辑是：

1. 遍历链表得到长度 len。
2. 有效移动步数为 k % len。
3. 找到第 len - (k % len) 个节点作为新链表的尾部。
4. 将原尾部连接到原头部形成环，再断开新尾部。

下面代码中使用了哑节点（dummy node）来简化边界处理，同时利用快慢指针定位断点。

public class RotateList {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;
        int len = 0;

        // 获取链表长度
        for (; fast.next != null; len++) {
            fast = fast.next;
        }

        // 确定需要移动的步数
        int step = len - k % len;
        for (int s = 0; s < step; s++) {
            slow = slow.next;
        }

        // 执行旋转：连成环后断开
        fast.next = dummy.next;
        dummy.next = slow.next;
        slow.next = null;
        return dummy.next;
    }

    public static void main(String[] args) {
        RotateList obj = new RotateList();
        int[] input = {1, 2, 3, 4, 5};
        ListNode initNode = ListNode.listNodeWithIntArray(input);
        System.out.println(initNode.toString());
        
        ListNode resultNode = obj.rotateRight(initNode, 2);
        System.out.println(resultNode.toString());
    }
}

这里的关键在于理解 fast 最终指向的是原链表的尾节点，而 slow 指向的是新链表的尾节点。一旦 fast.next 指向了 dummy.next（即原头节点），整个链表就变成了一个环，此时只需将 slow.next 置空即可切断环，完成旋转。

思路二：显式构建环形链表

上述方法虽然可行，但逻辑上可以进一步简化。既然要旋转，不如直接把链表首尾相接变成一个环。

1. 遍历链表找到尾节点并计算长度。
2. 将尾节点的 next 指向头节点。
3. 计算新的断点位置：len - k % len。
4. 从当前尾节点向后移动该步数，此时的节点即为新的尾节点。
5. 更新头节点为新尾节点的下一个节点，并将新尾节点的 next 置空。

这种方法不需要额外的哑节点，内存占用更优，逻辑也更直观。

public class RotateList {
    public ListNode rotateRightWithCircle(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        ListNode tail = head;
        int len = 1;

        // 计算长度并找到尾节点
        while (tail.next != null) {
            tail = tail.next;
            len++;
        }

        // 形成环
        tail.next = head;
        
        // 找到新的尾节点位置
        int step = len - k % len;
        while (step > 0) {
            tail = tail.next;
            step--;
        }
        
        // 断开环，返回新头
        head = tail.next;
        tail.next = null;
        return head;
    }

    public static void main(String[] args) {
        RotateList obj = new RotateList();
        int[] input = {1, 2, 3, 4, 5};
        ListNode initNode = ListNode.listNodeWithIntArray(input);
        System.out.println(initNode.toString());
        
        ListNode resultNode = obj.rotateRightWithCircle(initNode, 2);
        System.out.println(resultNode.toString());
    }
}

运行结果

控制台输出如下，可以看到链表确实完成了预期的旋转：

1-->2-->3-->4-->5-->Null
4-->5-->1-->2-->3-->Null

总结来说，处理链表旋转问题，关键在于识别出'旋转'本质上就是'断点移动'。通过取模处理大数 k，以及利用环形结构简化指针操作，可以在 O(n) 时间和 O(1) 空间内高效解决问题。