力扣61(java&python)-旋转链表(中等)
2022/9/17 1:18:36
本文主要是介绍力扣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
这篇关于力扣61(java&python)-旋转链表(中等)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署