61. Rotate List

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        # 0 1 2 3 4 5
        #     X     X
        if head is None:
            return head
        
        length = 0
        cur = head
        while(cur):
            length += 1
            cur = cur.next
        
        k = k % length
        if k == 0:
            return head # if k == 0, fast and slow will both stop at the end. then newHead would be None and no newHead.next should be called. so that we need to eliminate this situation first.
        
        fast = head
        for i in range(k):
            fast = fast.next
        
        slow = head
        while(fast.next):
            slow = slow.next
            fast = fast.next
            
        newHead = slow.next
        slow.next = None
        cur = newHead
        while(cur.next):
            cur = cur.next
        cur.next = head
        
        return newHead