社招有推链接吗
点赞 评论

相关推荐

核心思路是先统计链表总长度,确定需要反转的组数,再逐组局部反转并重新连接,计算出需要反转的组数s = n/k;然后循环s次,每次对当前 k 个节点进行局部反转,反转后将当前组的首尾与前后部分重新连接,最后返回处理后的链表头。对应的代码解析如下:class Solution {public:ListNode* reverseKGroup(ListNode* head, int k) {if(!head || k == 1) return head; // 空链表或k=1无需反转ListNode* dummy = new ListNode(0); // 虚拟头节点,简化头节点处理dummy->next = head;ListNode* cur = head;ListNode* pre = dummy; // 记录上一组的尾节点ListNode* next = nullptr;ListNode* prev = nullptr;ListNode* temp = nullptr; // 记录当前组反转前的头节点int n = 0;while(cur != nullptr) {n++;cur = cur->next;}cur = head;if(n == 1) return head; // 只有1个节点直接返回int s = n / k; // 计算需要反转的组数while(s--) {for(int i = 0; i < k; i++) {if(i == 0) temp = cur; // 记录当前组反转前的头节点next = cur->next;cur->next = prev; // 当前节点指向前一个反转节点prev = cur;cur = next;}pre->next = prev;temp->next = cur;pre = temp; // 更新上一组的尾节点为当前组反转前的头节点prev = nullptr; // 重置反转前驱指针}ListNode* newhead = dummy->next;delete dummy; // 释放虚拟头节点,避免内存泄漏return newhead;}};该解法的时间复杂度为 O (n),空间复杂度为 O (1)。
点赞 评论 收藏
分享
牛客网
牛客网在线编程
牛客网题解
牛客企业服务