Reverse Nodes in K-group

25.Reverse Nodes in k-Group

Linked List

Recursion

Problem Statement:

Given a linked list, reverse the nodes of a linked list k at a time and return its 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 is.

Example:

Input:

head = [1→2→3→4→5]
k = 2

→

Output:

[2→1→4→3→5]

Nodes are reversed in groups of 2. Last node stays as is.

Algorithm:

1. For each k-group:
   • Check if k nodes exist ahead (after pointer)
   • If not enough nodes, keep remaining as is
   • If k nodes exist, reverse the group
   • Connect with previous group (before pointer)
   • Connect with next group (after pointer)
2. Helper reverse function:
   • Standard reversal for exactly k nodes
   • Returns new head of reversed group

Complexity:

Time: O(n) | Space: O(1)

Java Solution:

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode trueHead = null;
    ListNode curr = head;
    ListNode before = null;
    ListNode after = null;
    
    while (curr != null) {
        int currK = k;
        
        // Find if k nodes exist ahead
        after = curr;
        while (after != null && currK-- > 0) 
            after = after.next;
        
        // If not enough nodes, keep remaining as is
        if (currK > 0) break;
                    
        // Reverse k nodes
        ListNode revGroup = reverse(curr, k);
        if (trueHead == null) trueHead = revGroup;
        
        // Connect with previous and next groups
        if (before != null) before.next = revGroup;
        curr.next = after;
        
        // Move pointers forward
        before = curr;
        curr = after;    
    }
    
    return trueHead;
}

// Helper to reverse exactly k nodes
public ListNode reverse(ListNode head, int k) {
    ListNode prev = null;
    ListNode curr = head;
    ListNode next;
    
    while (curr != null && k-- > 0) {     
        next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;  
    }
    
    return prev;
}

Python Solution:

def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
    true_head = None
    curr = head
    before = after = None
    
    while curr:
        # Check if k nodes exist
        after = curr
        count = k
        while after and count:
            after = after.next
            count -= 1
        
        if count: break  # Not enough nodes
        
        # Reverse group
        rev_head = self.reverse(curr, k)
        if not true_head:
            true_head = rev_head
            
        # Connect groups
        if before:
            before.next = rev_head
        curr.next = after
        
        # Move forward
        before = curr
        curr = after
        
    return true_head or head
    
def reverse(self, head: ListNode, k: int) -> ListNode:
    prev = None
    curr = head
    
    while curr and k:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
        k -= 1
        
    return prev

C++ Solution:

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode* true_head = nullptr;
    ListNode* curr = head;
    ListNode* before = nullptr;
    ListNode* after;
    
    while (curr) {
        // Check k nodes exist
        after = curr;
        int count = k;
        while (after && count) {
            after = after->next;
            count--;
        }
        
        if (count) break;
        
        // Reverse group
        ListNode* rev_head = reverse(curr, k);
        if (!true_head) true_head = rev_head;
        
        // Connect groups
        if (before) before->next = rev_head;
        curr->next = after;
        
        before = curr;
        curr = after;
    }
    
    return true_head ? true_head : head;
}

ListNode* reverse(ListNode* head, int k) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    
    while (curr && k) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
        k--;
    }
    
    return prev;
}