wordpress 企业站 模板,企业vi设计什么意思,常德网站开发,网络平台搭建是什么意思力扣题目#xff1a;旋转链表
开篇 今天是备战蓝桥杯的第25天和算法村开营第3天#xff01;经过这3天的学习#xff0c;感觉自己对链表的掌握程度大大地提升#xff0c;尤其是在帮村里的同学讨论相关问题时。本篇文章#xff0c;给大家带来一道旋转链表的题目#xff0c… 力扣题目旋转链表
开篇 今天是备战蓝桥杯的第25天和算法村开营第3天经过这3天的学习感觉自己对链表的掌握程度大大地提升尤其是在帮村里的同学讨论相关问题时。本篇文章给大家带来一道旋转链表的题目用到了巧妙的快慢指针方法
题目链接: 61.旋转链表
题目描述 代码思路 先用双指针策略找到倒数K的位置也就是{1,2,3}和{4,5}两个序列之后再将两个链表拼接成{4,5,1,2,3}就行了。具体思路是 因为k有可能大于链表长度所以首先获取一下链表长度,如果然后计算应该反转多少次0次则直接返回原链表。然后 1.快指针先走与反转次数相同的步。 2.慢指针和快指针一起走。 3.快指针走到链表尾部时慢指针所在位置刚好是要断开的地方。把快指针指向的节点连到原链表头部慢指针指向的节点断开和下一节点的联系。 4.返回结束时慢指针指向节点的下一节点。
代码纯享版
class Solution {public ListNode rotateRight(ListNode head, int k) {if(head null || k 0) return head;ListNode fast head, slow head;int sum 0;ListNode test head;while(test ! null){sum;test test.next;}if(k % sum 0)return head;int len k % sum;while(len 0){fast fast.next;len--;}while(fast.next ! null){fast fast.next;slow slow.next;}ListNode newhead slow.next;slow.next null;fast.next head;return newhead;}
}代码逐行解析版
class Solution {public ListNode rotateRight(ListNode head, int k) {if(head null || k 0) return head; //排除特殊情况如果不排除下面的k%sum中会出现sum0的报错ListNode fast head, slow head; //创建快慢指针int sum 0; ListNode test head; while(test ! null){ //利用test来遍历整个链表sum; //sum统计链表的长度test test.next;}if(k % sum 0)return head; //k是sum的整数倍反转完结果与原链表相同直接返回原链表int len k % sum; //计算出最终要分开的节点while(len 0){ //先让快指针领先慢指针len个结点fast fast.next; len--;}while(fast.next ! null){ //两个指针同时移动当快指针到尾结点时慢指针到达分开的位置fast fast.next;slow slow.next;}ListNode newhead slow.next; //三步操作让慢指针后面的部分拼接到头结点slow.next null;fast.next head;return newhead; //此时原本慢指针到下一个结点变成头结点返回它}
}其他解法
1.第一种是将整个链表反转,如实例1中,把链表变成{5,4,3,2,1}然后再将前K和N-K两个部分分别反转也就是分别变成了{4,5}和{1,2,3}这样就轻松解决了。
2.力扣官方题解提供了先将链表闭合为环然后寻找合适的位置断开的解法
class Solution {
public:ListNode* rotateRight(ListNode* head, int k) {if (k 0 || head nullptr || head-next nullptr) {return head;}int n 1;ListNode* iter head;while (iter-next ! nullptr) {iter iter-next;n;}int add n - k % n;if (add n) {return head;}iter-next head;while (add--) {iter iter-next;}ListNode* ret iter-next;iter-next nullptr;return ret;}
};结语 如果这道题的分享对您有所帮助点个关注为会每天更新力扣题的分享与大伙儿一同进步
