Microsoft 回文链表：O(1) 额外空间判定并恢复原链

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练版单向无环链表，节点值可比较相等；空链表视为回文。
• 返回 bool，调用后每个原节点的 next 指针和顺序完全恢复，而非只恢复值列表。
• O(1) 额外空间不计少量指针变量，不能复制节点或用值数组。

解题路线

1. 快慢指针从头走，fast 每次两步、slow 一步；fast 终止时 slow 位于偶数长度后半段起点，或奇数长度中点。
2. 奇数长度跳过中点，把第二半链原地反转；从头和反转后半段逐节点比较。
3. 无论比较结果如何都再次反转第二半链以恢复原链接，再返回结果；不能在发现不相等时直接 return。
4. 正确性：回文当且仅当前半序列等于后半逆序；双反转是恒等操作，第二次反转恢复节点 next。

手动走一遍

1→2→2→1 的后半 2→1 反转为 1→2，与前半 1→2 匹配，再恢复。1→2→3→2→1 跳过中间 3，比较两边 1→2。1→2→3 若第一对不等，也必须恢复后半才返回 False。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""Check a singly linked list palindrome in O(1) extra space and restore it."""

from dataclasses import dataclass


@dataclass(eq=False)
class ListNode:
    value: int
    next: "ListNode | None" = None


def _reverse(head: ListNode | None) -> ListNode | None:
    previous = None
    while head is not None:
        following = head.next
        head.next = previous
        previous, head = head, following
    return previous


def is_palindrome_restoring(head: ListNode | None) -> bool:
    if head is None or head.next is None:
        return True
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    second = slow.next if fast is not None else slow
    reversed_second = _reverse(second)
    left, right = head, reversed_second
    result = True
    while right is not None:
        if left.value != right.value:
            result = False
            break
        left, right = left.next, right.next
    _reverse(reversed_second)
    return result

复杂度

n 个节点：找中点、反转、比较、恢复各 O(n)，总 O(n) 时间；只用固定数量指针，O(1) 额外空间。

易错点与追问

容易失分的边界

• 借助数组存所有节点值却称 O(1) 空间。
• 奇数长度没跳过中点。
• 发现不相等时提前 return，留下被反转的调用方链表。
• 只恢复节点值而没恢复 next 指针身份关系。

继续深挖

• 链表可能有环时如何先检测？
• 只读链表不允许修改时，空间复杂度能否仍为 O(1)？
• 并发读者存在时，原地反转有什么风险？