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

力扣 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. 翻转链表：

   • 使用经典的链表翻转方法，通过三个指针 prev、curr 和 next 实现翻转。

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;}
};