Reverse Nodes in k-Group

How it works

We reverse the list one k-sized group at a time using pointers, without recursion.

Key ideas:

• Use a dummy node before the head to simplify edge cases.
• For each step, we:
  1. Find the k-th node from the current group's previous node.
     • If there aren't k nodes left, we stop (leave the rest as-is).
  2. Reverse the nodes in this k-sized segment.
  3. Re-connect the reversed segment back into the list.
  4. Move forward to the next group.

By repeating this process, we reverse every full group of k nodes while keeping the rest of the list intact.

Steps

1. Create a dummy node pointing to head. Set groupPrev = dummy (the node just before the current group).

2. Loop:

   • Use a helper getKth(groupPrev, k) to find the k-th node from groupPrev.
   • If kth is null, there are fewer than k nodes left → break.

3. Let:

   • groupNext = kth.next (first node after the current group).
   • prev = groupNext
   • curr = groupPrev.next (first node in the current group)

4. Reverse the current group:

   • While curr != groupNext:
     • Store curr.next in tmp.
     • Point curr.next to prev.
     • Move prev to curr.
     • Move curr to tmp.

5. After reversing:

   • groupPrev.next is now the start of the reversed group (kth node).
   • Store the original first node of this group (tmp = groupPrev.next before rewiring).
   • Set groupPrev.next = kth.
   • Move groupPrev = tmp (now the end of the reversed group).

6. Repeat steps 2–5 until no more full k-groups remain.

7. Return dummy.next as the new head of the list.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Forgetting to Handle Remaining Nodes

When there are fewer than k nodes remaining at the end of the list, they should be left as-is. A common mistake is attempting to reverse these remaining nodes anyway, which violates the problem requirements.

Incorrect Pointer Rewiring After Reversal

After reversing a k-group, you must correctly connect the reversed segment back to the rest of the list. Failing to update groupPrev.next to point to the new head of the reversed segment (which was the k-th node) results in a broken list.

Losing Track of the Original First Node

The original first node of each k-group becomes the last node after reversal. You need to save a reference to it before rewiring pointers, as it becomes the new groupPrev for the next iteration.

Off-by-One Errors When Counting k Nodes

When checking if there are at least k nodes available, ensure your counting logic is correct. Starting the count at 0 vs 1, or using < vs <= incorrectly, can cause you to reverse groups of the wrong size.

Not Using a Dummy Node

Without a dummy node before the head, handling the first k-group requires special case logic since there is no groupPrev node. Using a dummy simplifies the code and eliminates edge cases for updating the head of the list.

from typing import Optional

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        groupPrev = dummy

        while True:
            kth = self.getKth(groupPrev, k)
            if not kth:
                break
            groupNext = kth.next

            prev, curr = kth.next, groupPrev.next
            while curr != groupNext:
                tmp = curr.next
                curr.next = prev
                prev = curr
                curr = tmp

            tmp = groupPrev.next
            groupPrev.next = kth
            groupPrev = tmp
        return dummy.next

    def getKth(self, curr, k):
        while curr and k > 0:
            curr = curr.next
            k -= 1
        return curr

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* groupPrev = dummy;

        while (true) {
            ListNode* kth = getKth(groupPrev, k);
            if (!kth) {
                break;
            }
            ListNode* groupNext = kth->next;

            ListNode* prev = kth->next;
            ListNode* curr = groupPrev->next;
            while (curr != groupNext) {
                ListNode* tmp = curr->next;
                curr->next = prev;
                prev = curr;
                curr = tmp;
            }

            ListNode* tmp = groupPrev->next;
            groupPrev->next = kth;
            groupPrev = tmp;
        }
        return dummy->next;
    }

private:
    ListNode* getKth(ListNode* curr, int k) {
        while (curr && k > 0) {
            curr = curr->next;
            k--;
        }
        return curr;
    }
};