python-3.x - 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```

标签： python-3.xlinked-list

Answer 1

对于这个问题，我们可以使用Floyd 的 Tortoise and Hare算法，效率更高一些：

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