力扣题目:旋转链表
开篇
今天是备战蓝桥杯的第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中会出现sum==0的报错
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;
}
};
结语
如果这道题的分享对您有所帮助,点个关注,为会每天更新力扣题的分享,与大伙儿一同进步!
原文地址:https://blog.csdn.net/m0_73709096/article/details/134665182
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_4565.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!