CODEWITHSUNDEEP
pythonlistlinked-list
Bill Cheng
Bill Cheng

Reputation: 742

python linked list time limit exceed

I was doing some programming problems today on leetcode. The problem I was trying to solve is over on this link.

I was able to solve the problem using the code below:

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

However if I change to the code below, the online judges give me a time limit exceed error. I was wondering what the problem is over here.

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

I remembered I could do this in Java, but for some reason python can't do this.

Upvotes: 0

Views: 226

Answers (2)

Bill Cheng
Bill Cheng

Reputation: 742

I did some testing and found out that there was a infinity loop inside the code that was causing the time limit exceed error. In my code: oddPointer.next = head.next this line will always point back to itself.

Upvotes: 0

Robᵩ
Robᵩ

Reputation: 168726

In your second example, you have these three lines (I've removed all lines not relevant to the answer):

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

When the 2nd line is executed, oddPointer and head both refer to the same object. The line overwrites <that object>.next, i.e. it overwrites head.next. The original value of head.next is now irretrievably lost.

In your first example, you've stashed away the original value of head.next in the temp variable, so you can retrieve it later.

Upvotes: 1

Related Questions