https://leetcode.com/problems/reverse-nodes-in-k-group/submissions/1221405161/?envType=study-plan-v2&envId=top-interview-150

def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
	if not head: return head
	
	def reverse(node, k):
	    prev, curr = None, head
	    while k:
	        next_node = curr.next
	        curr.next = prev
	        prev = curr
	        curr = next_node
	        k -= 1
	    return prev
	
	ptr = head
	ktail = None
	
	new_head = None
	while ptr:
	    count = 0
	    ptr = head
	
	    # find the head of the start of the next k nodes
	    # so ptr will move forward until it points to the
	    # first node that is not part of the current k nodes
	    while count < k and ptr:
	        ptr = ptr.next
	        count += 1
	    
	    if count == k:
	        # returns the starting node of the current k nodes 
	        # that were just reveresed, this is the node that was
	        # originally right behind where ptr is right now
	        rev_head = reverse(head, k)
	        
	        # if this is the first set of k nodes we are reversing
	        # we need to make sure we store its "head" aka it's new
	        # starting node as the overall starting point of our linked
	        # list, since this is the node we have to return
	        if not new_head:
	            new_head = rev_head
	        
	        # if we already reversed a group of k nodes there will be
	        # a ktail, which we need to attach to the starting node
	        # of the new group of k nodes we just reversed
	        if ktail:
	            ktail.next = rev_head
	        
	        # k tail stores the last node of the current k nodes that
	        # was reversed. It will attach to the next set of nodes.
	        # we set ktail to head because before reversing, head used to be
	        # the starting point of the current k nodes, but after reversing
	        # it becomes the last node of the current k nodes
	        ktail = head
	        # move the head to the starting node of the next k nodes
	        head = ptr
	
	# if there is a ktail, attach it to head which stores the start of
	# next group of nodes
	if ktail:
	    ktail.next = head
	
	return new_head if new_head else head

/**
 * 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:
    // Reverse k nodes of the given linked list.
    ListNode* reverseLinkedList(ListNode* head, int k) {
        // This function assumes that the list contains at least k nodes.
        ListNode* new_head = nullptr;
        ListNode* ptr = head;
        
        while (k > 0) {
            // Keep track of the next node to process in the original list
            ListNode* next_node = ptr->next;
            
            // Insert the node pointed to by "ptr" at the beginning of the reversed list
            ptr->next = new_head;
            new_head = ptr;
            
            // Move on to the next node
            ptr = next_node;
            
            // Decrement the count of nodes to be reversed by 1
            k--;
        }
            
        // Return the head of the reversed list
        return new_head;
    }
            
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* ptr = head;
        ListNode* ktail = nullptr;
        
        // Head of the final, modified linked list
        ListNode* new_head = nullptr;
        
        // Keep going until there are nodes in the list
        while (ptr != nullptr) {
            int count = 0;
            
            // Start counting nodes from the head
            ptr = head;
            
            // Find the head of the next k nodes
            while (count < k && ptr != nullptr) {
                ptr = ptr->next;
                count += 1;
            }

            // If we counted k nodes, reverse them        
            if (count == k) {
                // Reverse k nodes and get the new head
                ListNode* revHead = reverseLinkedList(head, k);
                
                // new_head is the head of the final linked list
                if (new_head == nullptr)
                    new_head = revHead;
                
                // ktail is the tail of the previous block of reversed k nodes
                if (ktail != nullptr)
                    ktail->next = revHead;
                    
                ktail = head; 
                head = ptr;
            }
        }
        
        // Attach the final, possibly un-reversed portion
        if (ktail != nullptr)
            ktail->next = head;
        
        return new_head == nullptr ? head : new_head;
    }
};