0025. Reverse Nodes in k-Group¶
题目信息¶
- 题号:
K 个一组翻转链表
- 难度:
Hard
- 主题:
链表、分组、区间反转、递归
- 原题:
- 重点:
先确认完整分组,再原地反转半开区间,并保持不足 k 个节点的尾部不变
题目重述¶
给定单链表头节点 head 和正整数 k,从链表开头开始,每连续 k 个节点组成一组。反转每个完整分组
中的节点顺序,返回处理后的链表头节点。
若末尾剩余节点不足 k 个,这部分必须保持原顺序。必须通过修改 next 指针交换节点位置,不能只交换
节点值。
链表节点数量为 n,满足 1 <= n <= 5000;节点值位于 [0, 1000];1 <= k <= n。
自建示例¶
多个完整组与尾组:
head = [1,2,3,4,5,6,7]、k = 3,结果为[3,2,1,6,5,4,7];恰好分完:
head = [1,2,3,4,5,6]、k = 2,结果为[2,1,4,3,6,5];整条链表一组:
head = [4,8,1,9]、k = 4,结果为[9,1,8,4];分组大小为一:
head = [5,6,7]、k = 1,结果仍为[5,6,7];尾部不足一组:
head = [2,4,6,8,10]、k = 3,结果为[6,4,2,8,10]。
C++ 实现¶
class Solution {
private:
ListNode* recursiveGroups(ListNode* head, int k) {
ListNode* groupNext = head;
for (int count = 0; count < k; ++count) {
if (groupNext == nullptr) {
return head;
}
groupNext = groupNext->next;
}
ListNode* previous = recursiveGroups(groupNext, k);
ListNode* current = head;
for (int count = 0; count < k; ++count) {
ListNode* next = current->next;
current->next = previous;
previous = current;
current = next;
}
return previous;
}
ListNode* iterativeGroups(ListNode* head, int k) {
ListNode dummy(0, head);
ListNode* groupPrevious = &dummy;
while (true) {
ListNode* kth = groupPrevious;
for (int step = 0; step < k; ++step) {
kth = kth->next;
if (kth == nullptr) {
return dummy.next;
}
}
ListNode* groupStart = groupPrevious->next;
ListNode* groupNext = kth->next;
ListNode* previous = groupNext;
ListNode* current = groupStart;
while (current != groupNext) {
ListNode* next = current->next;
current->next = previous;
previous = current;
current = next;
}
groupPrevious->next = kth;
groupPrevious = groupStart;
}
}
public:
ListNode* reverseKGroup(ListNode* head, int k) {
return iterativeGroups(head, k);
}
};
题解¶
完整分组探测¶
一组只有在确实包含 k 个节点时才允许反转。若先修改指针,反转到一半后才发现节点不足,就必须恢复已经
改变的尾部链接,既增加状态,也容易破坏原链表。
迭代方法令 groupPrevious 指向当前组之前的节点,再从它出发向后移动 k 次:
成功到达
kth,说明groupPrevious->next到kth正好构成完整一组;中途到达空指针,说明剩余节点不足
k个,此时尚未改动任何链接,可以直接返回。
虚拟头节点使第一组也拥有普通前驱。即使第一组反转后真实头节点改变,最终仍统一返回 dummy.next。
四个分组边界¶
探测成功后,当前结构为:
... -> groupPrevious -> groupStart -> ... -> kth -> groupNext -> ...
四个指针分别表示:
groupPrevious:已处理前缀的尾节点;groupStart:当前组旧头;kth:当前组旧尾;groupNext:下一组首节点,可能为空。
当前组正是半开区间 [groupStart, groupNext)。使用右端不包含的区间后,反转循环可以直接以
current != groupNext 为终止条件,无需另外统计已经处理的节点数。
半开区间反转¶
普通链表反转通常令 previous 从空指针开始。本题令它从 groupNext 开始:
previous = groupNext
随后对当前组逐个执行:
next = current.next
current.next = previous
previous = current
current = next
第一次改写就让旧组头 groupStart 指向 groupNext。循环结束时,previous 指向新组头 kth,旧组头
已经成为新组尾并连接后缀。组内反转与后缀重连因此在同一个循环中完成,不需要反转结束后再次寻找组尾。
前缀重连与分组推进¶
反转完成后执行:
groupPrevious.next = kth
groupPrevious = groupStart
第一条链接把已处理前缀接到当前组的新头。第二条把 groupPrevious 移到当前组的新尾;由于
groupStart->next 已经指向原来的 groupNext,下一轮正好从下一组开始探测。
每轮开始时保持以下不变量:
dummy.next到groupPrevious已经按完整分组反转;groupPrevious->next开始的后缀尚未处理;已处理前缀与未处理后缀共同包含原链表全部节点,二者不重叠。
一次循环只消费未处理后缀的前 k 个节点,随后恢复同一不变量。因此每个完整组恰好反转一次;最后不足
k 个节点的尾部在探测失败前从未被修改,能够保持原顺序。
递归分组¶
recursiveGroups 使用相同的边界。它先向后探测 k 个节点;若不足一组,直接返回当前 head,把整个
尾部作为已经完成的结果。
存在完整组时,groupNext 指向下一组开头。递归调用先返回后缀处理后的头节点,再把这个返回值作为当前组
反转时的初始 previous。于是当前组旧头在第一次改写时就连接到已经处理好的后缀,最后返回当前组的新头。
迭代方法通过 groupPrevious 显式连接相邻分组,递归方法通过子调用返回值完成同一连接。公开入口采用迭代方法,
保留相同的分组结构,并消除随分组数量增长的调用栈。
复杂度分析¶
设链表长度为 n。迭代方法中,每个完整组的节点在探测和反转阶段各访问一次;不足一组的尾部只被最后一次
探测访问,因此总时间复杂度为 O(n),额外空间为 O(1)。
递归方法同样为 O(n) 时间。递归深度约为完整分组数量 O(n / k),每层只保存固定数量指针,因此调用栈
空间为 O(n / k);当 k = 1 时最坏为 O(n)。