Why does my Python linked-list reversal loop create a cycle?

Question

I'm trying to reverse a singly linked list in Python, but my loop does not terminate as expected. Here is the current implementation:

class Solution:
    def reverseList(self, head: ListNode | None) -> ListNode | None:
        p1 = head
        p2 = head.next
        if p2 is None or p1 is None:
            return head
        while p2 is not None:
            temp = p1.next
            p2.next = p1
            p2 = temp.next
            p1 = temp
        return head

What is causing the loop to behave incorrectly, and what is the correct way to reverse the list?

Yo Motherboard · Answer

The usual approach is to keep track of the previous node, the current node, and the next node. Save current.next before changing the link, then move all three references forward:

prev = None
curr = head

while curr is not None:
    nxt = curr.next
    curr.next = prev
    prev = curr
    curr = nxt

return prev

The returned node is prev because it becomes the new head of the reversed list.

Yo Motherboard · Answer

Your code links the second node back to the first, but it never properly detaches the original first node. With a list like 1 -> 2 -> 3, assigning p2.next = p1 creates 1  2, which is a cycle. You also return the old head instead of the new one.

A minimal correction is:

p1 = head
if p1 is None:
    return head

p2 = head.next
if p2 is None:
    return head

p1.next = None

while p2 is not None:
    temp = p2.next
    p2.next = p1
    p1 = p2
    p2 = temp

return p1

Here, p1 ends up pointing to the new head.

Yo Motherboard · Answer

Also, check for None before accessing head.next. If head is None, the original code raises an exception before reaching the condition that checks p1. In Python, use `is None` and `is not None` for None comparisons rather than `==` and `!=`.

Why does my Python linked-list reversal loop create a cycle?

Answers

Add your answer

Related Discussions