Python函数副作用问题：回文链表求解时原链表遭修改

你的问题核心有两个：

1. 链表是引用类型，original = head只是复制了指针，并没有复制整个链表结构。反转函数直接修改了原链表节点的next指针，导致原链表被破坏。
2. 最后head == reversed_是判断两个头节点的内存地址是否相同，而非链表的值是否一致，这本身就是错误的判断逻辑。

方案1：复制原链表后反转对比（空间复杂度O(n)） #

先遍历原链表，复制出一个完全独立的新链表，再反转这个新链表，最后逐个对比原链表与反转后链表的节点值。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        # 复制原链表生成独立新链表
        def copy_list(node):
            dummy = ListNode(0)
            curr = dummy
            while node:
                curr.next = ListNode(node.val)
                curr = curr.next
                node = node.next
            return dummy.next
        
        # 反转链表函数
        def reverse(arg):
            curr, prev = arg, None
            while curr:
                nxt = curr.next
                curr.next = prev
                prev = curr
                curr = nxt
            return prev
        
        # 复制后反转，避免修改原链表
        original_copy = copy_list(head)
        reversed_list = reverse(original_copy)
        
        # 逐个对比节点值
        while head and reversed_list:
            if head.val != reversed_list.val:
                return False
            head = head.next
            reversed_list = reversed_list.next
        # 两个链表必须都遍历完毕才是回文
        return head is None and reversed_list is None

方案2：快慢指针+反转后半段（空间复杂度O(1)，更优） #

不需要复制整个链表，用快慢指针找到链表中点，反转后半段链表后直接对比前半段与反转后的后半段，空间复杂度更低。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        # 反转链表函数
        def reverse(arg):
            curr, prev = arg, None
            while curr:
                nxt = curr.next
                curr.next = prev
                prev = curr
                curr = nxt
            return prev
        
        # 快慢指针找链表中点
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # 反转后半段：奇数长度时反转slow.next，偶数长度时反转slow
        reversed_half = reverse(slow.next if fast else slow)
        
        # 对比前半段与反转后的后半段
        while reversed_half:
            if head.val != reversed_half.val:
                # 可选：若需要还原原链表，可在此处再次反转reversed_half
                # reverse(reversed_half)
                return False
            head = head.next
            reversed_half = reversed_half.next
        
        # 可选：还原原链表
        # reverse(reversed_half)
        return True

方案2逻辑说明：

• 快慢指针：快指针每次走两步，慢指针走一步，快指针到末尾时，慢指针刚好指向链表中点。
• 反转后半段后，逐个对比节点值，全部相等则为回文。若要求不修改原链表，最后可将反转的后半段再次反转恢复结构。

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