反转 linkedList - 错误 - 在 ListNode 中找到循环

Question

我正在尝试反转单链表。这是我的代码。

def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if head is None:
        return None
    elif head.next is None:
        return head
    else:
        prev=None
        curr=head
        nextNode=curr.next
        
        while curr!=nextNode:
            prev = curr
            curr = nextNode
            if nextNode.next:
                nextNode = nextNode.next
            curr.next = prev

        head = curr
        return head

这是错误：错误 - 在 ListNode 中找到循环 我无法弄清楚哪一步导致了错误。

我使用了三个变量，即 prev、curr 和 nextNode 来遍历单链表，同时通过分配 curr.next=prev 来反转顺序。有人可以解释为什么会导致这个错误吗？

Answer 1

您的代码有几个问题：

1. 在移动到下一个节点之前，您没有正确地将

   curr.next

   更新为

   prev

   。

2. while curr!=nextNode:

   循环条件不正确；这不是检查列表的末尾，而是将当前节点与其下一个节点进行比较，这可能会导致循环。

这是更正后的版本：

from typing import Optional

# Assuming there is a definition for ListNode similar to this.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head: Optional[ListNode]) -> Optional[ListNode]:
    prev = None
    curr = head
    while curr:
        nextNode = curr.next  # Save next node
        curr.next = prev  # Reverse current node's pointer
        prev = curr  # Move pointers ahead for next iteration
        curr = nextNode
    return prev

这应该可以解决循环问题并正确反转列表。