回文链表

2025/10/16

思路：直接用栈，如果和顶上一样，就消掉，不一样就push，看看最后是不是正好能消掉

手写代码：

def Answer(head):
    stack = Stack()
    l = head
    while l != None:
        if l.val != stack.top():
            stack.push(l.val)
        elif l.val == stack.top():
            stack.pop()
        l = l.next
    
    return stack.empty()

答案：思路错误，与“相邻对称抵消”问题混淆。

思路2: 先遍历一遍确定长度，还是用栈，左半边一直push，右半边一直pop，看看能不能顺利进行

答案：思路正确，但有些细节待优化

推荐答案：

1. 在思路2中，遍历一遍之后就可以把链表变成数组了，访问更快，但付出了\(O(n)\)的空间代价。
2. 快慢指针，一个指针一倍速，一个指针两倍速，找到中点，然后就好操作了