61 Rotate List

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
# time O(2N) space O(1)
"""
main idea:connect tail with head to a circle and  get the length of LList. find tail and set tail.next to None to cut off the connection to new head of rotated LList 
note to loop to tail, instead of using k, need to use cnt-k 
"""
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        # edge case: k = 0 or head is empty
        if not head or k == 0:
            return head 
        p = ps = res = head 
        cnt = 1
        # find the tail and get length of LList. note the termination of finding the tail is p.next is None instead of p is None.  
        while p.next:
            p = p.next
            cnt += 1
            
        p.next = head # connect tail to the head 
        #k = cnt-k%cnt
        k = k%cnt # reduce unnecessary loop 
        if(k):
            for i in range(cnt - k): # tail node is cnt-k th node 
                p = p.next
        res = p.next 
        p.next = None 
        return res