💬 Discord
Sign In
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.