⚡Flashcard Drill➔
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

  1. Process the list in groups of k, but first check that a full group exists -- a partial trailing group must be left untouched.
  2. For each full group, reverse it with the standard three-pointer technique, using group_next (the node after the group) as the initial prev.
  3. Reconnect the previous group's tail to the new group head, and the new group tail to group_next.
  4. Repeat until fewer than k nodes 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 prev to None instead of group_next: the group's new tail must point at the next group, not at None.
  • 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.
🎯 Drill This Card Now➔

🧩 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           # 下一组的前驱