25. Reverse Nodes in k-Group

Solution 1: Iterative

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        listLen = 0
        ptrCurrent = head
        while ptrCurrent:
            listLen += 1
            ptrCurrent = ptrCurrent.next
            
        groupNum = listLen // k
        dummy = ListNode()
        dummy.next = head
        prevHead = dummy
        finalTail = head
        while groupNum:
            # Reverse group
            for idx in range(k - 1):
                nxtNode = finalTail.next.next
                # Reverse node, move the orig tail node to head 
                finalTail.next.next = prevHead.next
                prevHead.next = finalTail.next
                finalTail.next = nxtNode
            
            prevHead = finalTail
            finalTail = finalTail.next
            groupNum -= 1
        return dummy.next

Time Complexity: O(N)
Space Complexity: O(1)

Solution 2: Stack

Time Complexity: O(N)
Space Complexity: O(N)

Reference

https://leetcode.com/problems/reverse-nodes-in-k-group/discuss/11423/Short-but-recursive-Java-code-with-comments
https://blog.csdn.net/weixin_44737922/article/details/125764498?spm=1001.2101.3001.6650.15&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EOPENSEARCH%7ERate-15-125764498-blog-125905679.pc_relevant_multi_platform_whitelistv4&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EOPENSEARCH%7ERate-15-125764498-blog-125905679.pc_relevant_multi_platform_whitelistv4&utm_relevant_index=16