# 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
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