NeetCode #342LC-25HardLinked ListNC 150NC 250
← Back to All Problems#342 · #25 · Reverse Nodes in k-Group(K 个一组翻转链表)
📌 Problem Statement & Constraints
Given the head of a linked list, reverse the nodes
k at a time and return the modified list. If the number of nodes is not a multiple of k, the left-out nodes at the end stay as they are. You may not change node values. Constraints: 1 <= k <= n <= 5000.💡 Core Algorithmic Approaches
- Process the list in groups of
k, but first check that a full group exists -- a partial trailing group must be left untouched. - For each full group, reverse it with the standard three-pointer technique, using
group_next(the node after the group) as the initialprev. - Reconnect the previous group's tail to the new group head, and the new group tail to
group_next. - Repeat until fewer than
knodes remain.
💻 Benchmark Python3 Implementation
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
group_prev = dummy # node before the current group
while True:
# check that k nodes remain
kth = group_prev
for _ in range(k):
kth = kth.next
if not kth:
return dummy.next # fewer than k left -> done
group_next = kth.next # first node after the group
# reverse the group, linking the tail to group_next
prev, cur = group_next, group_prev.next
while cur != group_next:
cur.next, prev, cur = prev, cur, cur.next
# reconnect: group_prev -> new head (kth); old head is now the tail
tmp = group_prev.next
group_prev.next = kth
group_prev = tmp # move to the next group
return dummy.next⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each node is visited a constant number of times.
💾 Space Complexity
O(1): the reversal is done by relinking.
⚠️ Interview Pitfalls & Follow-ups
- Reversing the trailing partial group: the problem requires leaving it alone, so the lookahead check is essential.
- Forgetting to reconnect
group_prev: the reversed group would be detached from the rest of the list. - Initialising
prevtoNoneinstead ofgroup_next: the group's new tail must point at the next group, not atNone. - Losing the old head: it becomes the group's tail and the starting point for the next iteration, so it must be saved before the reconnection.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Linked List Problems
中文速览与面试要点
K 个一组翻转链表
给你链表的头节点 head,每 k 个节点一组进行翻转,请你返回修改后的链表。k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。进阶:你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗?约束:链表中的节点数目为 n;1 ≤ k ≤ n ≤ 5000;0 ≤ Node.val ≤ 1000。
核心要点
- 递归分组(标准解) :① 先检查剩余节点是否够 k 个,不够则直接返回 head(保持原序);② 反转前 k 个节点;③ 递归处理剩余部分并接到反转后的尾部。
- 为什么必须先检查长度 :不足 k 个的组不翻转,因此需要提前知道剩余长度。
- 反转的写法 :与 206 题相同,用 prev / cur / nxt 三指针,循环 k 次。
- 迭代版本(O(1) 空间) :用哑结点 + 记录每组的前驱,逐组反转并接回,可避免递归栈的 O(n/k) 空间。
常见陷阱
- 不检查剩余长度就反转 :会导致不足 k 个的尾组也被反转,违反题目要求。
- 返回 head 而非 prev : head 已变成该组的尾节点,新头是 prev 。
- 递归时忘记把 head.next 接到递归结果 :会导致链表断裂。
- 迭代版本中 group_prev 未更新 :处理完一组后,下一组的前驱是 这一组原来的头 (即现在的尾),必须用临时变量保存。
- 迭代版本中 prev 初始化为 group_next :反转后的尾节点应指向下一组的开头,因此 prev 的初值是 group_next 而非 None。
参考实现
class Solution:
def reverseKGroup(self, head: 'ListNode', k: int) -> 'ListNode':
# ① 检查剩余是否够 k 个
node = head
for _ in range(k):
if not node:
return head # 不足 k 个,保持原序
node = node.next
# ② 反转前 k 个节点
prev = None
cur = head
for _ in range(k):
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
# ③ 递归处理剩余部分,接到反转后的尾部
head.next = self.reverseKGroup(cur, k)
return prev # prev 是这一组的新头
# 迭代版本(O(1) 空间):
# dummy = ListNode(0, head)
# group_prev = dummy
# while True:
# kth = group_prev
# for _ in range(k):
# kth = kth.next
# if not kth: return dummy.next
# group_next = kth.next
# # 反转 group_prev.next .. kth
# prev, cur = group_next, group_prev.next
# for _ in range(k):
# nxt = cur.next
# cur.next = prev
# prev = cur
# cur = nxt
# tmp = group_prev.next
# group_prev.next = kth # 接上新头
# group_prev = tmp # 下一组的前驱