61. Rotate List

https://leetcode.com/problems/rotate-list/
Python

Time: O(N+k)
Space: O(1)
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        # Find the length
        length = 0
        end = head
        while end:
            length += 1
            end = end.next

        # Fine new_head and new_end
        new_head = head
        new_end = ListNode(next=head)
        for i in range(length - k % length):
            if new_head.next:
                new_head = new_head.next
            else:
                new_head = head

            if new_end:
                new_end = new_end.next
            else:
                new_end = head

        # Find break point
        cur = new_head
        while cur.next:
            cur = cur.next

        # Link break point to origin head
        # If new_end's next is None, means nothing moved
        if new_end.next:
            new_end.next = None
            cur.next = head

        return new_head
Python​

Python
