python linked list time limit exceed

Question

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.

Robᵩ · Accepted Answer · 2016-02-29 05:19:44Z

1

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.

answered Feb 29, 2016 at 5:19

Robᵩ

170k20 gold badges251 silver badges323 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Bill Cheng Over a year ago

Thanks for the answer!! I have a follow up question: in this case wouldn't there still be a value for head.next?

Bill Cheng · Accepted Answer · 2016-02-29 21:47:52Z

0

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.

edited Feb 29, 2016 at 21:47

answered Feb 29, 2016 at 16:48

Bill Cheng

7421 gold badge9 silver badges16 bronze badges

Collectives™ on Stack Overflow

python linked list time limit exceed

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related