为什么这个函数不返回True而是循环？

Question

我正在尝试解决这个链表问题： https://leetcode.com/problems/palindrome-linked-list/

我的代码适用于具有均匀数量节点的列表。当我尝试使用 If 语句更改它以推进节点时，代码开始循环。该代码在底部打印“here”，但不返回 True，而是循环并再次运行。

第二次运行时 tail.next = None 行出现错误。

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return True
        slow = fast = prev = head
        count = 0
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next
            count += 1

        if count % 2 == 1:
            prev = slow
            slow = slow.next
        
        curr = slow
        tail = curr
        start = prev
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        tail.next = None
        start.next = prev
        slow = fast = head
        for x in range(count):
            fast = fast.next
        while fast:
            if slow.val != fast.val:
                return False
            slow = slow.next
            fast = fast.next
        print('here')
        return True

Answer 1

有几个问题：

• if count % 2 == 1:

  毫无意义。我们可以想象，具有偶数个节点的列表和具有奇数个节点的列表之间存在细微差别，但是

  count

  并不代表列表中节点的数量：它代表列表中节点数量的一半。列表。并且该计数是奇数还是偶数没有相关意义。

• 与上一点相关，如果列表有两个节点，则

  count

  将为一个，因此您可以通过此

  slow

  块将

  None

  设置为

  if

  。这将导致执行

  tail.next = None

  时出现异常，因为此时

  tail

  是

  None

  。

• start.next = prev

  是一项危险的任务。如果前面的

  while

  循环仅进行一次迭代，则

  start == prev

  和此赋值将创建一个循环。如果通过删除

  tail.next = None

  来解决前一点以避免异常，并且输入是具有两个节点的列表，则会发生这种情况。程序将进入无限循环。

其他一些备注：

• 没有必要保留

  count

  。如上所述，当想要知道列表的奇偶性时，它没有任何作用。接近末尾的循环基于

  count

  ，可以用

  fast = prev

  替换，因为刚刚反转了后半部分，并使

  prev

  成为第二个列表的头部。

这是代码的修复：

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return True
        # Find center: no need for a counter
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # Reverse second half
        prev = None  # This is the way to ensure the reversed list ends with None
        while slow:
            next_node = slow.next
            slow.next = prev
            prev = slow
            slow = next_node

        # Compare halves, we can reuse `head`
        fast = prev  # No loop needed, we know where the second half starts
        while fast:
            if head.val != fast.val:
                return False
            head = head.next
            fast = fast.next
        return True