# Leetcode 61. Rotate list

## 題解

### Connect linked list to the cycle

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # Time complexity: O(n) -- Most two time traverse the list
        # Space complexity: O(1)
        # https://www.youtube.com/watch?v=UcGtPs2LE_c&t=440
        if k == 0 or not head or not head.next:
            return head
        
        # Example 1->2->3->4->5 , cur will be traverse to the 5, so this traversal will be pass four pointer, we start n at 1 ,so the end of result gonna be 5, witch is the linked list length.
        n = 1
        cur = head
        while cur.next:
            cur = cur.next
            n += 1
        
        k = k % n # This will minus repeat rotate.
        if k == 0: # If k equal 0 , means no need to rotate.
            return head
        tail = head # Tail will start at head.
        for i in range(n - k - 1): # n - k - 1 mean n = {[1->2->3] k = [4->5]} , minus 1 becase if start at first node, and k = 3 , so in the end the pointer will be pointing the 4 node, but we want pointing the node 3.
            tail = tail.next
        new_head = tail.next # tail's next is the new head
        tail.next = None # cut the tail
        cur.next = head # connect the origin head tail to the original head
        #       .tail
        # 1->2->3->4->5 -- tail in position
        #          .new_head

        #       .tail
        # 1->2->3 4->5 -- cut the tail
        #         .new_head

        #       .tail         .tail
        # 1->2->3 4->5->1->2->3 -- connect to the origin head
        #         .new_head
        return new_head