[61] Rotate List

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

• algorithms
• Medium (25.81%)
• Source Code: 61.rotate-list.py
• Total Accepted: 185.8K
• Total Submissions: 691.7K
• Testcase Example: '[1,2,3,4,5]\n2'

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

Example 1:

Input: 1->2->3->4->5->NULL, k = 2 Output: 4->5->1->2->3->NULL Explanation: rotate 1 steps to the right: 5->1->2->3->4->NULL rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

Input: 0->1->2->NULL, k = 4 Output: 2->0->1->NULL Explanation: rotate 1 steps to the right: 2->0->1->NULL rotate 2 steps to the right: 1->2->0->NULL rotate 3 steps to the right: 0->1->2->NULL rotate 4 steps to the right: 2->0->1->NULL

# 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 or not head.next: return head
        p = head
        length = 0
        while p:
            length += 1
            p = p.next

        k = k % length

        for i in range(k):
            head = self.rotateOneStep(head)

        return head

    def rotateOneStep(self, head):
        if not head or not head.next: return head
        p = head
        cur = head
        while p.next:
            cur = p
            p = p.next

        p.next = head
        cur.next = None

        return p


# [1,2,3], 2000000000
#
#
# #################################
# n1 = ListNode(1)
# n2 = ListNode(2)
# n3 = ListNode(3)
# n4 = ListNode(4)
# n5 = ListNode(5)
# n1.next = n2
# n2.next = n3
# n3.next = n4
# n4.next = n5
# head = n1
# s = Solution()
# head = s.rotateRight(head, 2)
# print head.val
# print head.next.val
# print head.next.next.val
# print head.next.next.next.val
# print head.next.next.next.next.val
#