题目描述 给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。 示例 1: 输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->1->2->3->NULL 解释: 向右旋转 1 步: 5->1->2->3->4->NULL 向右旋转 2 步: 4->5->1->2->3->NULL 示例 2: 输入: 0->1->2->NULL, k = 4 输出: 2->0->1->NULL 解释: 向右旋转 1 步: 2->0->1->NULL 向右旋转 2 步: 1->2->0->NULL 向右旋转 3 步: 0->1->2->NULL 向右旋转 4 步: 2->0->1->NULL https://leetcode-cn.com/problems/rotate-list/ 解法1 题目要求移动链表的k个元素，我们不妨先考虑只移动一个元素的情况。对于除了最后一个节点外的每个节点，我们都做以下动作。 备份下一个节点的值 将上一个节点的值覆盖到下一个节点 下一个节点的值作为“新的上一个节点的值” 移动到下一个节点 如果遇到最后一个节点，则将该节点的值覆盖到第一个节点上。下面我们用图来描述以下过程，下图以“1->2->3->4->5->NULL”为例。 上面的图描述了移动一个节点后的结果，当p指向倒数第二个节点时循环终止，此时nextBak=5。循环结束后，我们用nextBak覆盖掉头节点的值就完成了移动一个节点的过程。 我们还可以做一个优化，这个优化很容易想到。当移动次数k超过链表长度n时，我们只需要移动n%k个位置即可。下面的代码实现了上述全部过程。 解法2 上面的算法如果使用了优化，最多要移动n-1次单个元素。而移动单个元素的代价是移动链表中所有的元素，也就是n。因此，解法1的时间复杂度为O(n^2)。我们能不能只移动一次，来降低时间复杂度呢？ 我们通过计算找到链表的一个“切点”（图3的…