Reverse Nodes In K Group

Problem Description

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

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list’s nodes, only nodes themselves may be changed.

Examples

Constraints

• The number of nodes in the list is n.
• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

Segment Counting and In-Place Reversals

To reverse nodes in groups of k:

1. Count Remaining Nodes: Check if there are at least k nodes remaining in the list. If not, we return the current head (since the left-out nodes must remain as they are).
2. Reverse the Group: We reverse the next k nodes in-place. Let the curr node at the start of the group be the new tail of the reversed group.
3. Recursive Link: Once the k nodes are reversed, the new head is the last node of the group. We recursively call the function on the remaining list (curr.next = reverseKGroup(next_group_head, k)) and return the new head.

Solution 1: Recursive Segment Reversal

Verify segment capacity and reverse links recursively for each group.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode curr = head;
        int count = 0;
        
        // Verify if there are at least k nodes remaining
        while (curr != null && count < k) {
            curr = curr.next;
            count++;
        }

        if (count == k) {
            // Reverse the first k nodes
            curr = head;
            ListNode prev = null;
            for (int i = 0; i < k; i++) {
                ListNode next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }
            // Connect the reversed tail to the result of the remaining groups
            head.next = reverseKGroup(curr, k);
            return prev; // prev is the new head of the reversed group
        }
        return head; // less than k nodes remaining, leave unchanged
    }
}

# 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]:
        curr = head
        count = 0
        
        # Check if there are at least k nodes remaining
        while curr and count < k:
            curr = curr.next
            count += 1
            
        if count == k:
            # Reverse the first k nodes
            curr = head
            prev = None
            for _ in range(k):
                next_node = curr.next
                curr.next = prev
                prev = curr
                curr = next_node
            # Recurse for the remaining list
            head.next = self.reverseKGroup(curr, k)
            return prev  # prev is the new head of this reversed group
            
        return head  # less than k nodes, leave as is

/**
 * 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* curr = head;
        int count = 0;

        while (curr && count < k) {
            curr = curr->next;
            count++;
        }

        if (count == k) {
            curr = head;
            ListNode* prev = nullptr;
            for (int i = 0; i < k; i++) {
                ListNode* next = curr->next;
                curr->next = prev;
                prev = curr;
                curr = next;
            }
            head->next = reverseKGroup(curr, k);
            return prev;
        }
        return head;
    }
};

Complexity Analysis

• Time Complexity: O(n) since we visit each node at most twice (once to count, once to reverse).
• Space Complexity: O(n / k) due to the recursion call stack frames. (Can be optimized to O(1) space using an iterative wrapper).

Where It Breaks

If the recursion limit is very small (like in memory constrained embedded systems), recursive stack overflow is possible, and the iterative pointer redirection method must be used.

Common Mistakes

• Incorrect link connections: Failing to connect the tail of the current reversed segment to the head of the next segment.
• Wrong node count check: Attempting to reverse a segment that has fewer than k nodes, which violates the requirement to leave the tail elements unchanged.

← All Problems