这道题在 O(1)空间下可能完成么？

[20015jjw]

https://leetcode.com/problems/palindrome-linked-list/

我怎么觉得不能... 各位学过算法的球指点...

[IwfWcf]

可以做到，只是比较麻烦……

第一次遍历得到长度，确定中点；第二次遍历将中点之前的 list reverse，然后进行比较；第三次遍历将中点之前的 list 再次 reverse，恢复原始 list

[qw7692336]

创建多一条出来。

[qw7692336]

@qw7692336 不对不对，不允许这么做

[Andiry]

严格意义上不可能。任何需要修改原始输入的解法（比如原地reverse list）都不能算是O(1)空间复杂度。

[20015jjw]

@IwfWcf reverse就需要存储关于n变大二变大的数据啊... 不管是弄个pointer往前指 还是把数据存在外部结构里...

[sumhat]

如果递归不算额外空间的话，也是可以的。

[20015jjw]

@sumhat 如果利用额外空间不算的话，递归也是O(1)………

[zhyu]

@IwfWcf reverse和查找中点可以同时完成
@20015jjw reverse哪有那么多中间变量，就需要一个临时节点

[wy315700]

很简单啊

在操场上，两个人跑步，如果两个人速度不一样，那么，最终快的那个人会整整比慢的那个人快一圈的。
俗称套圈。

所以，弄两个指针，一个一次前进一步，一个一次前进两步，如果他们最终相遇了，那么就是存在环，否则就没有。

2011年银联面试题考过。

[wy315700]

不对，看错题了，无视我吧

[20015jjw]

@zhyu 一个linkedlist如果有10000个link，需要10000个额外的pointers，然而如果只有1个，那就只需要一个额外的pointers，这不就是O(n) space么....

[alafeizai]

@20015jjw 并没有多申请空间，而是利用了原有的next指针，只利用了一个中间变量做缓存。

[xcv58]

1L 正解

这题相当无聊。

[20015jjw]

@alafeizai 不懂... 我说的情况里长度为1和长度为10000的list需要的缓存一样多么？如果一样多，请问怎么实现呢？

[yangff]

不要慌。。上hash

[20015jjw]

@20015jjw

好吧现在懂了 reverse list的时候只是用了原来的pointer 唯一需要增加的只是指向中点的pointer...

但是还是有点虚... 因为上午问大神大神说算法课学过palindrome问题不能是O(1) space

[IwfWcf]

@zhyu 为什么可以同时完成？不先进行一次遍历怎么能知道 reverse 的时候在哪个节点停下来？

@20015jjw

node = head;
next = node->next;
while (next) {
tmp = next->next;
next->next = node;
node = next;
next = tmp;
}

[IwfWcf]

@zhyu 哦，知道了，用两个指针来移动

[zhyu]

@IwfWcf https://gist.github.com/zhyu/662d0a0aa88c5e21c31e
没写恢复指针的部分
恢复和判断也可以同时完成

[IwfWcf]

@zhyu 嗯，是的，这样就可以 AC 了？我之前用 C++ 交别的题的时候如果改变了传入的引用内容是会判错的