题目
25. K 个一组翻转链表
给你链表的头节点 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]
提示：
- 链表中的节点数目为 n
- 1 <= k <= n <= 5000
- 0 <= Node.val <= 1000
进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？
我的代码（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) {
if (!head || !head->next || k <= 1) {
return head;
}
ListNode* fakeHead = new ListNode(0, head);
ListNode* outerBeg = fakeHead;
ListNode* outerEnd = fakeHead->next;
ListNode* innerEnd = outerEnd;
int cnt = 0;
while(outerEnd) {
outerEnd = outerEnd->next;
cnt++;
if (cnt == k) {
innerEnd = outerBeg->next;
// reverse
ListNode* tmp0 = outerBeg;
ListNode* tmp1 = outerBeg->next;
ListNode* tmp2 = outerBeg->next->next;
while(tmp1 != outerEnd) {
tmp1->next = tmp0;
tmp0 = tmp1;
tmp1 = tmp2;
tmp2 = tmp2 ? tmp2->next : tmp2;
}
innerEnd->next = outerEnd;
outerBeg->next = tmp0;
outerBeg = innerEnd;
cnt = 0;
}
}
ListNode* result = fakeHead->next;
delete fakeHead;
return result;
}
};点评
没有特别的点，尤其是在两两翻转的题目之后。添加额外的头结点、用两个或者多个指针/索引遍历链表，有了这两个想法之后，很多题目都很容易处理。额外结点用于把特殊情况也能够纳入统一处理的程序；多个指针用于解决实际问题，包括不同速度遍历和固定距离遍历。难点大概在于如何处理各种边界条件。
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog