25. Reverse Nodes in k-Group

Description:

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 it is.

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

'''
[1] naive three pass)

idea::
1. calculate the total length of linked list
2. reverse total length//k times while linking
3. return head

- T/C: O(n) # n==len(linked list)
- S/C: O(1)
'''

'''
[2] one pass + one pass)

idea::
1. move end k times from head
1-1. if end reach None before k times, break
2. reverse [start, end)
3-1. if it is a firt time to reverse, change head to new head
3-2. else, link the last element of previous revesed list to new reversed list head
4. start again from step1

code::
it is same as below

-T/C: O(n) # for move end O(n), for reverse O(n), the total is two-pass
-S/C: O(1)
'''

# 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]:
        start=head
        end=head
        prev_last=start
        
        isInitial=True
        while end!=None:
            # moving end
            times=k
            while end!=None and times>0:
                end=end.next
                times-=1
            
            # if the length from start to end is less than k, break
            if times>0:
                break
            
            # reverse [start,end)
            new_tmp_head=self.reverse(start,k)
            
            # if it is a first time, change head
            if isInitial:
                head=new_tmp_head
                isInitial=False
            # else link the last element of previous revesed list to new reversed list head
            else:
                prev_last.next=new_tmp_head
            
            # iterative factors
            start.next=end
            prev_last=start
            start=end
            
        return head
        
        
    def reverse(self,start,k):
        prev=ListNode(-1,start) # dummy
        cur=start
        next=cur
        while k>0:
            next=cur.next
            cur.next=prev
            prev=cur
            cur=next
            k-=1
        return prev