526互联

力扣234-回文链表

发布时间 2023-12-22 12:57:09作者: metasequoiaa

难度：【简单】

  • 第一个想法是用栈，提交代码3次都显示解答错误。原因：第一次是没考虑一个节点的情况；第二次是不应该通过栈剩余元素个数判断单节点情况；第三次是没有考虑奇数个节点的情况。
  • 看官方题解，重新思考。用数组最容易解，时空复杂度都是O(n)。刚开始用栈是以为能优化到进阶的O(1)空间复杂度，其实是无法做到的。用快慢指针可以确定链表的前半段和后半段，通过反转其中半段链表可以得到O(1)的空间复杂度，但是感觉比较麻烦。
  • 想寻求更好的O(1)空间复杂度的算法，没想出来。。用数组写了一遍提交通过了。