Why am I getting a time out error even though I’ve specified for my Linked-list traversal to terminate?

Question

1.38M viewsSeptember 10, 2022linked-list python while-loop

1

hefu fhiwh September 7, 2022 0 Comments

I am reversing a singly- linked list with the following code:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        
        if not head: 
            return []
        
        curr = head.next
        prev = head

        while curr:
            curr.next = prev 
            curr = curr.next
            prev = prev.next
        
        return curr

I am getting a TIME OUT error- but I can’t seem to see the issue. When I run the loop on paper it seems to work fine, any ideas what is causing, what I assume is the loop to not terminate? Thanks

1 Answer

score 1 · Answer 1 · 2022-09-08T07:40:50+00:00

There are a few issues:

curr.next has already been modified by the time you do curr = curr.next. So instead of going forward in the list, you’re going backward (since curr.next is actually equal to prev by that time).
head.next is never modified, yet it should become None. You should actually start one step “earlier” in the list, making curr equal to head and prev should be None.
return curr is always going to return None, as that is the condition by which the while loop exits.

Here is a fix:

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        curr = head
        prev = None

        while curr:
            nxt = curr.next  # Remember what the next node is before losing the reference
            curr.next = prev  # Rewire.
            prev = curr  # Move the two references one step forward
            curr = nxt  # ... using the saved reference
        
        return prev   # Return what was the tail node, but now is the new head

So we use a temporary variable nxt here. You could also use tuple assignment… then you don’t need the explicit temporary variable:

        while curr:
            curr.next, prev, curr = prev, curr, curr.next