61. 旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/rotate-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

想法：

可以观察到每旋转一次就是让最后一个结点变成第一个结点，倒数第二个结点变成第二个结点，而且如果k>len，那么这个旋转结果是有规律的（or周期性），所以只要讨论一个周期即可。 观察第一个例子，len-k=3，所以第三个结点变成了最后一个 观察第二个例子，len-k%len=2，所以第二个结点变成了最后一个 由此可以写出代码：

class Solution { public: ListNode* rotateRight(ListNode* head, int k) { if(!head||!head->next||k==0) return head; int len=1; ListNode* last = head; while(last->next) { len++; last = last->next; } int temp = len - k%len; ListNode* newend = head; while(temp-1) { newend = newend->next; temp --; } last->next = head; head = newend->next; newend->next = nullptr; return head; } };