力扣 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]
解题思路
这道题的核心是分组翻转链表,需要注意以下几点:
-
虚拟头节点:
- 使用虚拟头节点
dummy
简化边界条件处理,特别是头节点的翻转。
- 使用虚拟头节点
-
分组翻转:
- 遍历链表,每次找到
k
个节点作为一组。 - 对每一组进行翻转,并将翻转后的子链表重新连接到主链表中。
- 遍历链表,每次找到
-
翻转链表:
- 使用经典的链表翻转方法,通过三个指针
prev
、curr
和next
实现翻转。
- 使用经典的链表翻转方法,通过三个指针
-
边界条件:
- 如果剩余节点不足
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;}
};