超过 Python 链表时间限制

Question

我今天在leetcode上做了一些编程问题。我试图解决的问题在此链接上结束了。

我能够使用以下代码解决问题：

class Solution(object):
    def oddEvenList(self, head):
        if not head:
            return head
        oddPointer = head
        evenPointer = head.next
        temp = head.next
        while evenPointer and evenPointer.next:
            oddPointer.next = evenPointer.next
            oddPointer = oddPointer.next
            evenPointer.next = oddPointer.next
            evenPointer = evenPointer.next
        oddPointer.next = temp
        return head

但是，如果我更改为下面的代码，在线评委会给我一个时间限制超过错误。我想知道这里有什么问题。

class Solution(object):
    def oddEvenList(self, head):
        if not head:
            return head
        oddPointer = head
        evenPointer = head.next
        while evenPointer and evenPointer.next:
            oddPointer.next = evenPointer.next
            oddPointer = oddPointer.next
            evenPointer.next = oddPointer.next
            evenPointer = evenPointer.next
        oddPointer.next = head.next #this is the change
        return head

我记得我可以在Java中做到这一点，但由于某种原因，python不能做到这一点。

Answer 1

在你的第二个例子中，你有这三行（我已经删除了所有与答案无关的行）：

oddPointer = head
oddPointer.next = evenPointer.next
oddPointer = head.next

执行第 2 行时，oddPointer 和 head 都引用同一对象。该行覆盖<that object>.next，即覆盖head.next。 head.next的原始价值现在已不可挽回地丢失。

在第一个示例中，您已将 head.next 的原始值隐藏在 temp 变量中，以便稍后检索它。

Answer 2

我做了一些测试，发现代码中有一个无穷大循环导致时间限制超过错误。在我的代码中：oddPointer.next = head.next此行将始终指向自身。