如何判断一个单链表是否为回文链表？

直接回答：最直观的做法是把值复制到数组后双指针对撞，时间 O(n)、空间 O(n)。进阶要求是 O(1) 空间：快慢指针找到中点，反转后半段链表，与前半段逐点比较，最后（可选）把后半段再反转恢复结构。

展开解析：O(1) 空间版本把三个基础操作串成了一条流水线：1）快慢指针找中点——fast 每次两步、slow 每次一步，fast 到尾时 slow 在中点（注意奇偶长度的处理）；2）反转链表——迭代三指针；3）双头比较。任何一步单独拿出来都是独立面试题，所以这道题常用来考察基本功的组合运用。易错点：奇数长度时中点节点不属于任何一半、比较只需走完较短的一半、以及面试中如果允许改结构才用反转法，否则应说明副作用。追问方向：如何用递归（调用栈当栈）实现 O(n) 空间的优雅写法、回文判断扩展到「重排链表」「回文对」等变体。

示例：

def is_palindrome(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    prev = None                       # 反转后半段
    while slow:
        slow.next, prev, slow = prev, slow, slow.next
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left, right = left.next, right.next
    return True