力扣61(java&python)-旋转链表（中等）

题目：

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

解题思路：

快慢指针+闭环

整体思路：找到倒数第k个结点的前一个结点，然后让链表的尾结点连接首结点形成闭环，然后倒数第k个结点是新链表的头结点，它之前的前一个结点作为链表的尾结点。

 具体思路（结合例子）：

1.定义慢指针slow和快指针fast，初始都指向链表的头结点；

 2.让快指针走到链表的尾结点处，计算出链表的长度len，将尾结点指向head形成闭环；

 3.计算出慢指针需要移动的步数step，移动慢指针,移动step – 1步，使慢指针在倒数第k个结点的前一个结点；

 4.保存慢指针slow的下一个结点，作为新链表的头结点，并断开它与下一个结点的联系，使其指向空，让它作为新链表的尾结点；

 

 5.返回新的头结点即可。

注解：

1.len从1开始：因为快指针初始化的时候就在头结点上，因此长度初始值就应该为1。

2.对下断代码的解释：结合上面的例子，算出来的slow的步数step=5，但是实际slow只移动4步，因为链表是环形，需要把结点4和结点4的前一个结点断开，但是不清楚结点4的前一个结点是谁，故这里就少移动一步，指向结点3，并保存结点4，方便后面断开3和4的联系。

  while(step-- > 1){
            slow = slow.next;
        }

java代码：

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode() {}
 7  *     ListNode(int val) { this.val = val; }
 8  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 9  * }
10  */
11 class Solution {
12     public ListNode rotateRight(ListNode head, int k) {
13         //特判
14         if(head == null || k == 0) return head;
15         int len = 1;
16         ListNode fast = head, slow = head;
17         //计算链表长度
18         while(fast.next != null){
19             len++;
20             fast = fast.next;
21         }
22         //将链表变成环
23         fast.next = head;
24         //计算出慢指针需要移动的步数
25         int step = len - k%len;
26         while(step-- > 1){
27             slow = slow.next;
28         }
29         //保存慢指针的下一个结点（新的头结点）
30         ListNode newHead = slow.next;
31         //断开闭环
32         slow.next = null;
33         return newHead;
34     }
35 }

 python3代码：

 1 # Definition for singly-linked list.
 2 # class ListNode:
 3 #     def __init__(self, val=0, next=None):
 4 #         self.val = val
 5 #         self.next = next
 6 class Solution:
 7     def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
 8         # 特判当k为0或者链表长度为0或1
 9         if not head or not head.next or k == 0:
10             return head
11         # 定义快慢指针和长度
12         fast, slow = head, head
13         len = 1
14         # 计算链表长度
15         while fast.next:
16             len += 1
17             fast = fast.next
18 
19         #形成闭环
20         fast.next = head
21 
22         # 移动慢指针
23         step = len - k%len - 1
24         # 条件是当step为0停止循环，故step要先减1
25         while step:
26             slow = slow.next
27             step -= 1
28         # 保存当前慢指针等下一个结点作为新的头结点
29         newHead = slow.next
30         slow.next = None
31         return newHead