LeetCode Rotate List

LeetCode解題之Rotate List

原題

將一個鏈表中的元素向右旋轉k個位置。

注意點：

例子：

輸入: list = 1->2->3->4->5->NULL, k = 2

輸出: 4->5->1->2->3->NULL

解題思路

如果能有鏈表的長度，就不用擔心k非常大而不斷的循環旋轉了。所謂的旋轉其實就是在鏈表中間斷開，首尾相連。在獲取鏈表長度的時候順便把鏈表的首尾連起來。注意斷開的位置是在倒數第k個之前。

AC源碼

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

    def myprint(self):
        print(self.val)
        if self.next:
            self.next.myprint()


class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not head:
            return []
        curr = head
        length = 1
        while curr.next:
            curr = curr.next
            length += 1
        curr.next = head
        cur = head
        shift = length - k % length
        while shift > 0:
            curr = curr.next
            shift -= 1
        result = curr.next
        curr.next = None
        return result


if __name__ == "__main__":
    l1 = ListNode(1)
    l2 = ListNode(2)
    l3 = ListNode(3)
    l4 = ListNode(4)
    l5 = ListNode(5)
    l1.next = l2
    l2.next = l3
    l3.next = l4
    l4.next = l5
    result = Solution().rotateRight(l1, 2)
    result.myprint()