將一個鏈表中的元素向右旋轉k個位置。
注意點:
k可能非常大 最好不要申請額外空間例子:
輸入: list = 1->2->3->4->5->NULL, k = 2
輸出: 4->5->1->2->3->NULL
如果能有鏈表的長度,就不用擔心k非常大而不斷的循環旋轉了。所謂的旋轉其實就是在鏈表中間斷開,首尾相連。在獲取鏈表長度的時候順便把鏈表的首尾連起來。注意斷開的位置是在倒數第k個之前。
# 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()