当前位置: 首页> 科技> 数码 > 建站工具 营销_能下载各种应用的软件_网页代码_品牌定位

建站工具 营销_能下载各种应用的软件_网页代码_品牌定位

时间:2025/7/9 23:17:26来源:https://blog.csdn.net/weixin_50893711/article/details/146095290 浏览次数:0次
建站工具 营销_能下载各种应用的软件_网页代码_品牌定位

力扣 Hot 100 刷题记录 - K 个一组翻转链表

题目描述

K 个一组翻转链表 是力扣 Hot 100 中的一道经典题目,题目要求如下:

给你链表的头节点 head,每 k 个节点一组进行翻转,请你返回修改后的链表。

k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,请将最后剩余的节点保持原有顺序。

你不能只是单纯地改变节点内部的值,而是需要实际进行节点交换。

示例 1:
输入:head = [1,2,3,4,5], k = 2
输出:[2,1,4,3,5]

示例 2:
输入:head = [1,2,3,4,5], k = 3
输出:[3,2,1,4,5]


解题思路

这道题的核心是分组翻转链表,需要注意以下几点:

  1. 虚拟头节点

    • 使用虚拟头节点 dummy 简化边界条件处理,特别是头节点的翻转。
  2. 分组翻转

    • 遍历链表,每次找到 k 个节点作为一组。
    • 对每一组进行翻转,并将翻转后的子链表重新连接到主链表中。
  3. 翻转链表

    • 使用经典的链表翻转方法,通过三个指针 prevcurrnext 实现翻转。
  4. 边界条件

    • 如果剩余节点不足 k 个,则保持原有顺序。

C++ 代码实现

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {ListNode* dummy = new ListNode(0); // 虚拟头节点dummy->next = head;ListNode* prev = dummy; // 前一个节点ListNode* curr = head;  // 当前节点while (curr) {// 检查剩余节点是否足够 k 个ListNode* tail = curr;int count = 0;while (tail && count < k) {tail = tail->next;count++;}// 如果不足 k 个,直接返回if (count < k) {break;}// 翻转 k 个节点ListNode* newHead = reverseList(curr, tail);prev->next = newHead; // 将翻转后的子链表连接到主链表prev = curr;          // 更新 prevcurr = tail;          // 更新 curr}return dummy->next; // 返回新链表的头节点}private:// 翻转从 head 到 tail 之间的链表(不包含 tail)ListNode* reverseList(ListNode* head, ListNode* tail) {ListNode* prev = nullptr;ListNode* curr = head;while (curr != tail) {ListNode* next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;}
};
关键字:建站工具 营销_能下载各种应用的软件_网页代码_品牌定位

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: