python - 这里超出时间限制的原因是什么

Question

给定一个链表，将链表向右旋转 k 个位置，其中 k 是非负数。

这里有些例子：

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

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

代码：

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if k < 0:
            return head

        if head is None or head.next is None:
            return head
        it = head
        while k != 0:
            while it.next.next is not None:
                it = it.next
            temp = it.next
            it.next = None
            temp.next = head
            head = temp
            it = head
            k -= 1
        return head

上面的代码适用于k < 2000000。

失败的测试用例是 -

Last executed input:

[1,2,3]

2000000000

Error: Time Limit Exceeded

时间复杂度将是 O(k* 列表长度)，对吗？

标签： pythonlinked-listnodes