Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

Example

Given 1->2->3->4->5 and k = 2, return 4->5->1->2->3.

Solution

难点，当前指针挪动到第K个，然后在快慢指针同时移动到末尾，注意head.next. 这样就是后面有第k个节点。

小技巧： tail.next == 右数K个位置。

for i in range(k):

head = head.next

while head.next:

    head = head.next

    tail = tail.next

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

class Solution:
    # @param head: the list
    # @param k: rotate to the right k places
    # @return: the list after rotation
    def getLen(self,head):
        index = 0
        while head:
            index = index + 1
            head = head.next
        return index

    def rotateRight(self, head, k):
        # write your code here
        if head == None:
            return None
        k = k % self.getLen(head)

        dummy = ListNode(0)
        dummy.next = head
        head = dummy
        tail = head 

        for i in range(k):
            head = head.next

        while head.next:
            head = head.next
            tail = tail.next 

        head.next = dummy.next
        dummy.next = tail.next
        tail.next = None

        return dummy.next