Why does my Python linked-list reversal loop fail to terminate?
Asked by
MellowCedar42
I'm trying to reverse a singly linked list in Python, but my loop behaves incorrectly and appears not to terminate. My current approach uses two pointers, p1 and p2, and updates node links inside the loop. Here is the code:
class Solution:
def reverseList(self, head: ListNode | None) -> ListNode | None:
p1 = head
p2 = head.next
if p2 == None or p1 == None:
return head
while p2 != None:
temp = p1.next
p2.next = p1
p2 = temp.next
p1 = temp
return head
What is causing the loop or list structure to break, and what is the correct way to reverse the list?
Answers
The usual iterative solution keeps three references: the previous node, the current node, and the next node. Save current.next before changing it, point current backward, then advance both pointers. The new head is prev, not the original head:
prev = None
curr = head
while curr is not None:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prev
Your code changes p2.next before safely preserving the rest of the list, and it also returns the old head instead of the new one.
Reply to this answer
There is also a small safety issue before the loop: p2 = head.next is executed before checking whether head is None. An empty list would therefore raise an AttributeError. Check head first, or use the standard prev/current approach, which naturally handles both an empty list and a one-node list. For comparisons with None, prefer `is None` and `is not None` rather than `== None` and `!= None`.
Reply to this answer
With a list such as 1 -> 2 -> 3, setting p2.next = p1 changes the link to 2 -> 1, but node 1 still points to node 2. That creates a cycle between the first two nodes. You also set p2 to temp.next rather than simply advancing it to the saved next node, which skips nodes and can eventually dereference None.
If you want to keep the two-pointer style, detach the old head first and advance through the saved node:
if head is None:
return None
p1 = head
p2 = head.next
p1.next = None
while p2 is not None:
temp = p2.next
p2.next = p1
p1 = p2
p2 = temp
return p1
Reply to this answer
Add your answer
Answers are reviewed before publication.
Related Discussions