Why is the time limit exceeding in reversing the linked list?

Question

# Definition for singly-linked list.

 class ListNode:

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

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev=ListNode(-1,head)
        curr=head
        dummy=head
        while dummy.next:
            curr.next=prev
            prev=dummy
            dummy=dummy.next
            curr=dummy
        return prev

I created three nodes, I used the prev and curr node for reversing and the dummy node for traversing ahead in the original linked list but I am getting time limit exceeded. I would like to know my logical error in this method

Answer 1

Some issues:

• In the loop you modify the node's next attribute before saving the original next reference. So once that is done, you have lost all possibility to move forward in list, and dummy=dummy.next will now walk back since at the start of the iteration, dummy was equal to curr.

• It is undesired to create a new node with value. Your code would link back to it in the first iteration of the loop. And because of the first problem, dummy becomes prev, which has a next reference to where you came from, creating an infinite loop. Instead of this -1 Node, just initialise prev as None.

• The while condition is wrong. The loop should continue until you reach the very last node, so when curr is None.

• Not a major issue, but why call that node reference dummy? There is nothing dummy about it. Use a name that describes what it references, for instance nextNode or nxt for short.

Correction:

class Solution:
    def reverseList(self, head):
        prev=None  # Don't create a new node
        curr=head
        while curr:  # Continue until the *last* node
            nxt=curr.next  # Save the next reference
            curr.next=prev
            prev=curr
            curr=nxt  # ... so you can move ahead
        return prev