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,看看能不能顺利进行
答案:思路正确,但有些细节待优化
推荐答案:
- 在思路2中,遍历一遍之后就可以把链表变成数组了,访问更快,但付出了\(O(n)\)的空间代价。
- 快慢指针,一个指针一倍速,一个指针两倍速,找到中点,然后就好操作了