25. Reverse Nodes in k-Group

# 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: ListNode, k: int) -> ListNode:
        """ tc O(N) sc O(N//K)
        recursively loop  per k LList segment, and meanwhile reverse each k LList
        keep the new_head at each recursion and linked back to its previous segment LList's tail 
        """
        if not head:
            return None
        a,b = head,head
        for i in range(k):
            if not b:
                return a
            b = b.next
        # a--b is a segment LList with k length 
        # new tail is a.next 
        new_head = self.reverse(a,b)
        a.next = self.reverseKGroup(b,k)
        return new_head
    
    def reverse(self,start,end):
        prev,cur,nxt = None,start,None
        while cur != end :
            nxt = cur.next
            cur.next = prev 
            prev = cur 
            cur = nxt
        return prev 
        

# 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: ListNode, k: int) -> ListNode:
        """ tc O(N) sc O(1)
        main idea: use l,r to define range of each segment LList at length of k; use jump  to keep tracking each reversed segment LList  
        """
        dummy = jump = ListNode()
        l = r = head
        while True:
            cnt = 0 
            while r and cnt < k:  
                r = r.next
                cnt += 1 
            if cnt == k:
                pre, cur = r, l 
                for _ in range(k):
                    nxt = cur.next
                    cur.next = pre
                    pre = cur 
                    cur = nxt 
                jump.next = pre
                jump = l
                l = r
                    
            else:
                return dummy.next