你最经典的手撕题！

🧩 面试手撕题：判断回文链表

题目描述：

给定一个单链表的头节点 head，判断该链表是否为回文链表。

如果是返回 true，否则返回 false。

示例：

• 输入：1 -> 2 -> 2 -> 1输出：true
• 输入：1 -> 2输出：false

💡 面试官想考什么

• 是否熟悉 链表基本操作
• 是否能想到 O(1) 额外空间 的做法
• 边界条件是否考虑全面

🧠 解题思路（适合白板讲）

1. 用 快慢指针 找到链表中点
2. 反转后半部分链表
3. 从头和中点同时向后比较
4. 有不等就返回 false

✍️ 代码示例（Java / C++ / Python 思路通用）

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def isPalindrome(head):
    if not head or not head.next:
        return True

    # 1. 快慢指针找中点
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # 2. 反转后半部分
    prev = None
    while slow:
        nxt = slow.next
        slow.next = prev
        prev = slow
        slow = nxt

    # 3. 比较前后两部分
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left = left.next
        right = right.next

    return True

⚠️ 常见翻车点

• 忘记处理 奇数长度链表
• 只会用数组存再判断（空间复杂度偏高）
• 指针顺序写反，现场容易慌

🧠 面试加分点

如果时间允许，可以主动说一句：

“如果要求不破坏原链表结构，可以在比较完后再反转回来。”