Что является причиной превышения лимита времени здесь - PullRequest
Новая
       21

Что является причиной превышения лимита времени здесь

1 голос
/ 20 февраля 2020

Учитывая связанный список, поверните список вправо на 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 </strong>.

Неудачный тестовый пример - 

Last executed input:

[1,2,3]

2000000000

Error: Time Limit Exceeded

Сложность времени быть O (k * длина списка), правильно?

...