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