25. K 个一组翻转链表
一句话套路数够 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 <= 50000 <= Node.val <= 1000
进阶:你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗?
思路
时间
O(n)空间
O(1)思路
先探路确认剩余够 k 个(不够就保留原序),再反转这一组。
反转时把 prev 初值设为 groupNext,反转完自然接上了后段。
groupPrev 只在本组完成后前移一次,移到「本组原来的尾结点」。
易错
反转后本组的头尾互换,记 tail = 原头 才能正确接下一组。
图解
链表结构(来自本仓库测试数据)
C++17 题解
namespace lc0025 {
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode dummy(0);
dummy.next = head;
ListNode* groupPrev = &dummy;
while (true) {
ListNode* kth = groupPrev;
for (int i = 0; i < k && kth; ++i) kth = kth->next;
if (!kth) break; // 不足 k 个,保持原序
ListNode* groupNext = kth->next;
ListNode* prev = groupNext; // 反转时组尾直接接上后段
ListNode* cur = groupPrev->next;
while (cur != groupNext) {
ListNode* nxt = cur->next;
cur->next = prev;
prev = cur;
cur = nxt;
}
ListNode* groupTail = groupPrev->next; // 旧的组头,现在是组尾
groupPrev->next = kth; // 新的组头接到前一段
groupPrev = groupTail;
}
return dummy.next;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0025::Solution s;
ListNode* a = buildList({1, 2, 3, 4, 5});
CHECK_EQ(listToVec(s.reverseKGroup(a, 2)), vector<int>{2, 1, 4, 3, 5});
ListNode* b = buildList({1, 2, 3, 4, 5});
CHECK_EQ(listToVec(s.reverseKGroup(b, 3)), vector<int>{3, 2, 1, 4, 5});
ListNode* c = buildList({1, 2, 3, 4, 5});
CHECK_EQ(listToVec(s.reverseKGroup(c, 1)), vector<int>{1, 2, 3, 4, 5});
ListNode* d = buildList({1, 2, 3});
CHECK_EQ(listToVec(s.reverseKGroup(d, 4)), vector<int>{1, 2, 3}); // k 超过长度