三个月算法进阶--day20

length = 1
ptr = head
while ptr.next:
    ptr = ptr.next
    length += 1

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head or k == 0:
            return head
        length = 1
        ptr = head
        while ptr.next:
            length += 1
            ptr = ptr.next
        point = k % length
        if point == 0:
            return head
        prev_len = length - point
        n = 1
        start = head
        while n < prev_len:
            start = start.next
            n += 1
        ans = start.next
        start.next = None
        start = ans
        while start.next:
            start = start.next
        start.next = head
        return ans

class Solution:
    def rotateRight(self, head: 'ListNode', k: 'int') -> 'ListNode':
        # base cases
        if not head:
            return None
        if not head.next:
            return head
        
        # close the linked list into the ring
        old_tail = head
        n = 1
        while old_tail.next:
            old_tail = old_tail.next
            n += 1
        old_tail.next = head
        
        # find new tail : (n - k % n - 1)th node
        # and new head : (n - k % n)th node
        new_tail = head
        for i in range(n - k % n - 1):
            new_tail = new_tail.next
        new_head = new_tail.next
        
        # break the ring
        new_tail.next = None
        
        return new_head