leetcode61:旋转链表

给你一个链表的头节点 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]

提示：

• 链表中节点的数目在范围 [0, 500] 内
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 109

步骤 1：题目分析

1. 输入条件：

   • 一个单向链表的头节点 head 和一个整数 k。
   • 链表的节点数目在 [0, 500] 的范围内。
   • 节点的值范围在 [-100, 100] 之间。
   • k 的范围可以大到 2 * 10^9，所以需要处理非常大的 k 值。

2. 输出条件：

   • 返回旋转后的链表的头节点，链表节点顺序需向右移动 k 个位置。

3. 边界条件：

   • 空链表或只有一个节点的链表不需要旋转。
   • 当 k 值大于链表长度时，可以用 k % 链表长度 的结果来替代 k 进行旋转，减少计算量。

步骤 2：解决思路

1. 确定链表的长度：首先遍历链表，计算链表长度 n。
2. 简化旋转步数：
   • 如果 k 大于 n，只需旋转 k % n 次即可，因为每 n 次旋转会使链表回到原始位置。
3. 将链表连接成环：
   • 将链表的尾节点指向头节点，这样可以将旋转操作转化为在环上找到新的起始点。
4. 找到新的头节点：
   • 计算旋转后的新尾节点位置 n - k % n - 1。
   • 将新尾节点的 next 设为 None，使链表断开，形成新的头尾链表。
5. 时间复杂度：由于我们只需遍历链表两次，因此时间复杂度为 O(n)。
6. 空间复杂度：该方法不需要额外的空间，空间复杂度为 O(1)。

C++ 实现代码

步骤 4：启发与优化

• 时间复杂度优化：通过构建环来实现旋转，比逐一移动节点更高效。
• 循环利用：利用 k % n 缩小旋转次数，避免多余的操作。
• 空间优化：无需额外的数组存储链表节点，通过原地修改实现空间优化。

步骤 5：实际应用场景

这种旋转链表的方法在许多实际场景中都可以用到，比如在调度系统或数据轮询中。例如，在任务调度中，经常需要实现循环调度，即将任务列表的顺序向右或向左移动，以均衡负载。通过这种方法可以有效地实现任务的优先级旋转或资源的负载均衡，从而提升系统的稳定性和效率。