61.旋转链表

1.题目描述

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

2.解题思路

通过示例1，我们可以发现一个规律：

• 向右旋转1个位置， 其实就是把原链表最后一个元素5，从原来的链表中拿下来，放到了原链表的头部；
• 向右旋转2个位置，其实就是把原链表的最后两个元素4->5,摘下来，链接到原链表的头部;
• 那么如果向右旋转k个位置，其实就是把原链表最后k个元素从原链表中断开，重新链接到原链表的头部；

通过示例2，我们还可以发现另一个规律：

• 当我们旋转的步数k>n,其中n为链表中的元素个数时，其实真正有效的旋转次数为k%n次，即链表中有3个元素，旋转4个位置，其实就等价于旋转4 % 3 = 1个位置

那么本题思路就很清晰了，我们需要先求出链表的元素个数n，使得k%=n，从而得到有效的旋转次数。接下来就找倒数第n-k的元素的位置，以及它的前一个位置，因为我们要将它从原链表中断开，所以就需要使用它的前一个位置pre,令pre.next = null;找到这个位置cur后，还要找从它开头的最后一个元素的位置，因为我们要把它重新挂到链表的头部，假设这个位置为p,即p.next = head;最终以cur开头的新链表，就是原链表向右旋转k个位置的结果。

3.代码实现

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode rotateRight(ListNode head, int k) {if (head == null) {return head;}//首先,需要统计出链表中结点个数,k %= n即为有效旋转次数int n = 0;ListNode p = head;while (p != null) {n += 1;p = p.next;}k %= n;if (k == 0) {return head;}//pre指向需要断开位置的前一个位置//cur指向需要断开的位置//旋转k次即为 从cur开始往后的链表 需要放到最前面ListNode pre = null;ListNode cur = head;int i = 0;while (i < n - k) {pre = cur;cur = cur.next;i += 1;}pre.next = null;//使用指针p去找cur的末尾位置p = cur;while (p.next != null) {p = p.next;}p.next = head;return cur;}
}