链表回文判断代码异常：输入[1,1,2,1]返回错误结果True

你的reverseLL函数是原地反转链表，调用它之后原链表的结构会被彻底修改——原本的头节点会变成反转后链表的尾节点（next被设为None），整个原链表的指针指向完全反转。

以输入[1,1,2,1]为例：

• 调用reverseLL(head)后，原head指向的第一个1的next变为None，反转后的链表头temp是最后一个1，链表结构为1->2->1->1。
• 此时对比head和temp，循环只会执行1次（因为head.next已经是None），仅对比了第一个元素就返回True，完全没检查到后面的1和2不匹配。

方案1：复制原链表后再反转（保留原思路） #

先复制出一个和原链表完全相同的新链表，反转新链表后再和原链表对比，这样原链表结构不会被修改。

新增复制链表函数 #

def copyLL(head):
    if not head:
        return None
    new_head = Node(head.data)
    current = new_head
    original_current = head.next
    while original_current:
        current.next = Node(original_current.data)
        current = current.next
        original_current = original_current.next
    return new_head

修改回文判断函数 #

def checkpalindrome(head):
    copied_head = copyLL(head)
    temp = reverseLL(copied_head)
    current_original = head
    current_reversed = temp
    
    while current_original and current_reversed:
        if current_original.data != current_reversed.data:
            return False
        current_original = current_original.next
        current_reversed = current_reversed.next
    return True

方案2：快慢指针+反转后半段（空间最优） #

不需要复制整个链表，用快慢指针找到链表中间节点，反转后半段后对比前半段和反转后的后半段，最后恢复原链表结构，空间复杂度为O(1)。

完整代码 #

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def find_middle(head):
    slow = head
    fast = head
    # 快指针走两步，慢指针走一步，定位中间节点
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

def reverseLL(head):
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

def checkpalindrome(head):
    if not head or not head.next:
        return True
    
    # 找到中间节点
    middle = find_middle(head)
    # 反转后半段链表
    reversed_half = reverseLL(middle)
    temp_reversed = reversed_half  # 保存反转后的头，用于恢复原链表
    
    # 对比前半段和反转后的后半段
    is_palindrome = True
    current = head
    while current and reversed_half:
        if current.data != reversed_half.data:
            is_palindrome = False
            break
        current = current.next
        reversed_half = reversed_half.next
    
    # 恢复原链表结构
    reverseLL(temp_reversed)
    
    return is_palindrome

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