谭谭心怎么建设网站,网络推广服务合同模板,重庆企业黄页大全电话,叫人开发网站注意事项力扣题目链接 首先我们考虑一种很直观的思路#xff1a; 遍历链表#xff0c;统计链表长度遍历链表#xff0c;进行翻转 对于每一组长度为 K 的节点#xff0c;进行翻转如果剩余节点不足 K 个#xff0c;则不进行翻转 连接翻转后的子链表 这里我们用的就是只用 O(1) 额外内… 力扣题目链接 首先我们考虑一种很直观的思路 遍历链表统计链表长度遍历链表进行翻转 对于每一组长度为 K 的节点进行翻转如果剩余节点不足 K 个则不进行翻转 连接翻转后的子链表 这里我们用的就是只用 O(1) 额外内存空间的算法 关于如何 k 个节点个数的链表
我认为这里最重要的是链表的翻转当你知道需要翻转的链表长度的时候这个方法应该按照固定模版来进行也就是我们的三指针
for (int i 1; i k; i) {cur-next nex-next;nex-next pre-next;pre-next nex;nex cur-next;
}但是还记得我们之前在做反转链表题目的时候是怎么处理的嘛
while (cur) {ListNode *nex cur-next;cur-next pre;pre cur;cur nex;
}这里简单直观多了最大的区别是什么呢 首先做整表翻转的时候我们的逻辑非常简单 其次对于对 k 个节点分组翻转并且我们还必须做到对剩余的 k 个节点不进行翻转势必有这样形式的代码 while (cout k) {...for (...) {...}...count - k;
}CPP总体代码
class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {if (!head || k 1) return head;ListNode *dummyHead new ListNode();dummyHead-next head;ListNode *cur dummyHead, *pre dummyHead, *nex dummyHead;int count 0;cur head;while (cur) {cur cur-next;count;}while (count k) {cur pre-next;nex cur-next;for (int i 1; i k; i) {cur-next nex-next;nex-next pre-next;pre-next nex;nex cur-next;}pre cur;count - k;}return dummyHead-next;}
};
