25. Reverse Nodes In K-group

The Reverse Nodes in k-Group problem (LeetCode 25) is a popular “Hard” linked list problem and a common benchmark in FAANG (Meta, Amazon, Google) and top tech interviews. It frequently appears in mid-to-senior level rounds, often as a follow-up to basic linked list reversal.

This problem is especially valued because it tests efficient, in-place linked list manipulation, filtering out naive approaches like array conversions. More importantly, it reinforces three essential linked list patterns:

1. Sublist reversal: The logic of reversing a segment of a list.
2. Boundary management between groups: Connecting the tail of one reversed group to the head of the next.
3. The dummy node pattern: Handling edge cases where the original head of the list is moved.

It is one of the best problems for testing whether you truly understand pointer manipulation in linked lists. The core pattern here is in-place reversal of a linked list applied to fixed-size groups, which requires careful bookkeeping of where each group starts, ends, and connects to the next.

Problem statement

Given the head of a singly linked list and an integer k, reverse the nodes of the list k at a time and return the modified list.

Specifically, take the first k nodes, reverse their order, then take the next k nodes, reverse their order, and so on. If the number of remaining nodes at the end is fewer than k, leave those nodes in their original order.

You may not alter the values stored in the nodes. Only the node links themselves may be changed.

Constraints

• 1 ≤ k ≤ n ≤ 5000, where n is the number of nodes in the list.
• 0 ≤ Node.val ≤ 1000

Examples

Why naive approaches fail in Reverse Nodes in k-Group

A naive approach is to convert the linked list into an array, split it into groups of size k, reverse each group, and then rebuild the list. While this works, it uses O(n) extra space, which goes against the core goal of linked list interview questions, testing in-place manipulation.

Another inefficient approach is repeatedly scanning from the head to find group boundaries. This leads to O(n × k) time complexity in the worst case, since nodes are revisited multiple times.

In coding interviews, especially for FAANG-level linked list problems, interviewers expect an O(n) time and O(1) space solution. The focus is on handling pointer manipulation and in-place reversal efficiently in a single pass through the linked list.

Optimized approach: In-Place reversal using dummy node

The key idea is to process the linked list in a single pass using a dummy node technique along with in-place reversal of nodes in groups of size k. The dummy node points to the head of the list and helps simplify edge cases, especially when the first group is reversed.

For each group, we first verify that at least k nodes are available. If so, we reverse exactly k nodes in place by iteratively updating pointers within the group. Once a group is reversed, we connect the previous group’s tail to the new head of the reversed segment. We then update our pointers and move forward to process the next group until the end of the list.

This is a classic in-place linked list manipulation pattern, where instead of creating new nodes or using extra memory, we efficiently reorganize existing next pointers to achieve the result in O(n) time and O(1) space.

Why the optimized approach works well

Each node in the linked list is visited only a constant number of times, once during the check for k nodes and once during the in-place reversal process. This ensures an overall O(n) time complexity.

The dummy node simplifies the implementation by removing special-case handling for the head of the list. It allows consistent pointer logic throughout all groups.

By maintaining a pointer to the node just before each group, often referred to as group_prev, we always know where to connect the reversed segment. After each reversal, the original first node of the group becomes the last node, which naturally serves as the new group_prev for the next iteration. This structure ensures clean pointer updates and efficient traversal without extra space or redundant work.

Step-by-step algorithm

1. Create a dummy node and set its next pointer to head. Initialize group_prev to the dummy node.
2. Iterate through the list, and from group_prev, check whether there are at least k nodes ahead.
3. If fewer than k nodes remain, stop the process as no further reversal is needed.
4. Mark group_prev.next as the first node of the current group, which will become the tail after reversal.
5. Reverse exactly k nodes starting from the first node of the group using the standard iterative reversal technique with prev and curr pointers.
6. After reversal, connect group_prev.next to the new head of the reversed segment (the prev pointer after the reversal loop).
7. Connect the original first node (now the tail) to the node that follows the reversed group (the curr pointer after the reversal loop).
8. Update group_prev to the original first node (the current group’s tail), which is now positioned just before the next group.
9. Repeat the process until all possible groups are processed.
10. Return dummy.next as the new head of the modified list.

1 / 9

Python implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def reverse_k_group(head: ListNode, k: int) -> ListNode:
    # Create a dummy node to simplify head manipulation
    dummy = ListNode(0)
    dummy.next = head
    group_prev = dummy

    while True:
        # Check if there are at least k nodes remaining
        kth = group_prev
        for i in range(k):
            kth = kth.next
            if not kth:
                # Fewer than k nodes remain, we are done
                return dummy.next

        # Save the node after the current group
        group_next = kth.next

        # Reverse k nodes in place
        prev = group_next  # After reversal, first node points to group_next
        curr = group_prev.next
        for i in range(k):
            tmp = curr.next
            curr.next = prev
            prev = curr
            curr = tmp

        # Connect the previous part to the new head of reversed group
        # The original first node is now the tail of this group
        tail_of_reversed = group_prev.next
        group_prev.next = prev  # prev is now the head of the reversed segment

        # Move group_prev to the tail of the current reversed group
        group_prev = tail_of_reversed


# Helper functions for testing
def build_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    curr = head
    for v in values[1:]:
        curr.next = ListNode(v)
        curr = curr.next
    return head


def list_to_array(head):
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result


# Driver code with 5 test cases

if __name__ == "__main__":

    # Test case 1
    head = build_list([1, 2, 3, 4, 5])
    k = 2
    result = reverse_k_group(head, k)
    print("Input: [1, 2, 3, 4, 5]\nk = 2")
    print("Output:", list_to_array(result), "\n\n")  # Expected: [2, 1, 4, 3, 5]

    # Test case 2
    head = build_list([1, 2, 3, 4, 5])
    k = 3
    result = reverse_k_group(head, k)
    print("Input: [1, 2, 3, 4, 5]\nk = 3")
    print("Output:", list_to_array(result), "\n\n")  # Expected: [3, 2, 1, 4, 5]

    # Test case 3
    head = build_list([1, 2, 3])
    k = 1
    result = reverse_k_group(head, k)
    print("Input: [1, 2, 3]\nk = 1")
    print("Output:", list_to_array(result), "\n\n")  # Expected: [1, 2, 3]

    # Test case 4
    head = build_list([1, 2, 3, 4])
    k = 4
    result = reverse_k_group(head, k)
    print("Input: [1, 2, 3, 4]\nk = 4")
    print("Output:", list_to_array(result), "\n\n")  # Expected: [4, 3, 2, 1]

    # Test case 5
    head = build_list([1])
    k = 1
    result = reverse_k_group(head, k)
    print("Input: [1]\nk = 1")
    print("Output:", list_to_array(result), "\n\n")  # Expected: [1]

Time complexity

The algorithm processes each node a constant number of times. The counting step visits each node once across all iterations, and the reversal step visits each node once as well. This gives us O(n) time complexity overall, where n is the total number of nodes in the linked list. The inner loops run k iterations each, and there are at most n / k groups, so total work is O((n/k) x k) = O(n).

Space complexity

The algorithm uses O(1) auxiliary space. All pointer manipulations happen in place without allocating new nodes or using data structures that grow with input size. There is no recursion, so no stack space is consumed beyond a fixed number of pointer variables.

Edge cases

• k equals 1: No reversal occurs since every group is a single node. The list is returned unchanged.
• k equals n (list length): The entire list is reversed as one group.
• Single node list: With one node, regardless of k (which must be 1 given the constraint k ≤ n), the list remains the same.
• Last group has fewer than k nodes: These trailing nodes must remain in their original order, not partially reversed.

Common pitfalls

• Losing the connection between groups: After reversing a group, candidates often forget to link the previous group’s tail to the new head of the reversed segment, resulting in a broken list.
• Off-by-one errors in counting: Miscounting the k nodes ahead leads to either reversing too many nodes or failing to detect that a full group exists.
• Forgetting to update group_prev: After processing a group, group_prev must advance to the tail of the just-reversed group. Failing to do this causes infinite loops or incorrect connections.
• Incorrectly initializing prev in the reversal loop: The prev pointer should start as the node after the current group (not None), so that the tail of the reversed segment connects to the rest of the list.