leetcode61:旋转链表

原题地址：61. 旋转链表 - 力扣（LeetCode）

题目描述

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

示例 2：

输入：head = [0,1,2], k = 4
输出：[2,0,1]

解题思路

1. 明确旋转规则：

   • 每次旋转，将链表的最后一个节点移到链表头部。
   • 如果 kk 大于链表长度，实际旋转次数为 k%链表长度k%链表长度。

2. 处理边界条件：

   • 链表为空，单节点，或 k=0k=0：直接返回原链表。
   • kk 为链表长度的倍数时，旋转后链表不变。

3. 实现方案：

   • 使用一个 ArrayList 将链表节点存储起来，方便操作和索引。
   • 循环 k%链表长度k%链表长度 次，每次从尾部移除一个节点，将其插入到头部。
   • 最终返回列表的第一个节点作为新的链表头。

源码实现

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        // 边界条件判断
        if (null == head || head.next == null || k == 0) {
            return head; // 空链表、单节点链表或无需旋转时，直接返回原链表
        }

        // 使用 ArrayList 存储链表节点
        List<ListNode> nodeList = new ArrayList<>();
        ListNode node = head;
        while (null != node) { // 遍历链表并存储每个节点
            nodeList.add(node);
            node = node.next;
        }

        // 链表长度
        int length = 0;
        if (k <= nodeList.size()) {
            length = k; // 当 k 小于等于链表长度时，旋转次数等于 k
        } else {
            // 当 k 大于链表长度时，旋转次数取 k % 链表长度
            length = k % nodeList.size() == 0 ? nodeList.size() : k % nodeList.size();
        }

        // 执行旋转操作
        for (int i = 0; i < length; i++) {
            int index = nodeList.size() - 1; // 当前链表的最后一个节点索引
            ListNode prev = nodeList.get(index - 1); // 倒数第二个节点
            ListNode curr = nodeList.get(index); // 最后一个节点

            // 移动最后一个节点到头部
            nodeList.remove(index); // 移除最后一个节点
            prev.next = null; // 将倒数第二个节点设置为尾节点
            curr.next = nodeList.get(0); // 最后一个节点指向原链表头部
            nodeList.add(0, curr); // 将最后一个节点插入到列表头部
        }

        // 返回新链表头节点
        return nodeList.get(0);
    }
}

复杂度分析

1. 时间复杂度：

   • 遍历链表并存储节点到 ArrayList：O(n)O(n)，其中 nn 是链表长度。
   • 每次旋转操作：
     • 从 ArrayList 中移除尾节点和插入头部操作为 O(1)O(1)。
     • 循环 k%nk%n 次，最坏情况下 k=nk=n，最多旋转 nn 次。
   • 总时间复杂度：O(n+k%n)O(n+k%n)，在最坏情况下为 O(2n)O(2n)。

2. 空间复杂度：

   • 使用了一个 ArrayList 存储链表节点，空间复杂度为 O(n)O(n)。
   • 总空间复杂度：O(n)O(n)