Rotate List

Problem: Rotate List

We can use two pointers to quickly locate rotate point and cut and re-link to achieve the answer. One pointer going k step ahead of another. When the fast one gets to the end, the slow one is at what we want. Besides, if k is a really big number, we need to calculate k mod length of list, which means we need to know length of our linked list first.

Code in Python:

# 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
        """
        if not head: return head

        p, length = head, 0
        while p:
            p = p.next
            length += 1
        k = k % length
        if not k: return head

        slow, fast = head, head
        for i in xrange(k):
            fast = fast.next
        while fast.next:
            slow, fast = slow.next, fast.next
        ans, slow.next, fast.next = slow.next, None, head
        return ans