LeetCode 234回文链表判断函数无法返回True陷入循环问题排查

问题分析 #

你的代码在处理偶数长度链表时正常，但添加奇数节点处理逻辑后出现两个问题：

• 程序陷入循环，打印here后无法正常返回
• 第二次运行时tail.next = None触发错误

核心错误点如下：

1. 奇偶长度判断逻辑错误
   用count % 2 == 1判断链表是奇数长度完全不可靠：count是慢指针移动的次数，奇数长度的链表对应的count值可能是奇数或偶数（比如3个节点count=1，5个节点count=2）。正确的判断方式是看循环结束后fast是否不为None——奇数长度时fast会停在最后一个节点，偶数长度时fast为None。

2. 反转链表时初始prev赋值错误
   反转后半部分链表时，你复用了之前循环的prev变量（前半部分最后一个节点或中间节点），导致反转后的链表和前半部分连在一起形成环，这是程序陷入循环的根本原因。反转链表的初始prev应该设为None。

3. 奇数处理时的变量赋值错误
   处理奇数长度时，错误地将prev更新为中间节点，导致后续连接反转后的链表时出错，应该只让slow跳过中间节点，prev保持为前半部分的最后一个节点。

修复后的代码 #

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return True
        
        slow = fast = head
        prev = None
        # 找到链表中点，prev记录前半部分的最后一个节点
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next
        
        # 奇数长度时，跳过中间节点
        if fast:
            slow = slow.next
        
        # 反转后半部分链表
        curr = slow
        reverse_prev = None
        tail = curr  # 记录反转前的后半部分头，即反转后的尾
        while curr:
            next_node = curr.next
            curr.next = reverse_prev
            reverse_prev = curr
            curr = next_node
        
        # 将反转后的尾节点next置空，避免成环
        if tail:
            tail.next = None
        
        # 比较前半部分和反转后的后半部分
        p1 = head
        p2 = reverse_prev
        while p2:
            if p1.val != p2.val:
                return False
            p1 = p1.next
            p2 = p2.next
        
        return True

关键修正说明 #

• 奇偶判断：用if fast:替代count % 2 == 1，准确识别奇数长度链表，跳过中间节点。
• 反转链表：使用独立的reverse_prev变量初始化为None，确保反转后的链表是独立的，不会和前半部分形成环。
• 变量隔离：将反转逻辑的变量与前半部分遍历的变量分开，避免变量复用导致的逻辑混乱。
• 环的避免：反转后将原后半部分的头（反转后的尾）的next置空，彻底切断循环引用。

内容的提问来源于stack exchange，提问作者user22673187