Leetcode Medium:旋转链接列表

Question

这是我写的，(是的，这不是最理想的答案(但有时我会遇到超时异常。

# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
if (head != None):
while (k > 0):
cur = head
if (head.next == None):
prev = head
else:
while (head.next != None):
prev = head
head = head.next
prev.next = None
head.next = cur
k -= 1
return head```

Answer 1

我们可以使用Floyd的乌龟和兔子算法来解决这个问题，效率更高：

class Solution:
def rotateRight(self, head, k):
if not head:
return
if not head.next:
return head
curr, length = head, 1
while curr.next:
curr = curr.next
length += 1
k %= length
if k == 0:
return head
slow = fast = head
for _ in range(k):
fast = fast.next
while fast.next:
slow, fast = slow.next, fast.next
temp = slow.next
slow.next = None
fast.next = head
head = temp
return head