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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 3420 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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

指点

完成

空间

24 条回复 • 2015-07-13 16:39:01 +08:00

IwfWcf

2015-07-13 01:28:50 +08:00

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

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

qw7692336

2015-07-13 01:48:17 +08:00

创建多一条出来。

qw7692336

2015-07-13 01:48:46 +08:00

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

Andiry

2015-07-13 02:03:12 +08:00

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

20015jjw

2015-07-13 02:16:50 +08:00

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

sumhat

2015-07-13 03:01:46 +08:00

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

20015jjw

2015-07-13 03:59:59 +08:00 via Android

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

zhyu

2015-07-13 07:08:58 +08:00 via iPhone

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

wy315700

2015-07-13 07:46:51 +08:00

很简单啊

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

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

2011年银联面试题考过。

wy315700

2015-07-13 07:48:19 +08:00

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

20015jjw

2015-07-13 09:36:02 +08:00

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

alafeizai

2015-07-13 09:54:16 +08:00

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

xcv58

2015-07-13 09:56:49 +08:00

1L 正解

这题相当无聊。

20015jjw

2015-07-13 10:08:38 +08:00 via Android

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

yangff

2015-07-13 10:20:05 +08:00 via Android

不要慌。。上hash

20015jjw

2015-07-13 10:31:34 +08:00 via Android

@20015jjw

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

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

IwfWcf

2015-07-13 10:33:55 +08:00

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

@20015jjw

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

IwfWcf

2015-07-13 10:38:55 +08:00

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

zhyu

2015-07-13 11:27:13 +08:00

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

IwfWcf

2015-07-13 13:27:33 +08:00

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

zhyu

2015-07-13 14:23:55 +08:00

@IwfWcf 题目链接？我不记得遇到过不能改传入值的题。。

IwfWcf

2015-07-13 15:29:37 +08:00

@zhyu 找不出来了，当时也没有特别记录，和这题类似最后 return bool，但我改了传入的 vector 的内容就被判错

ffffwh

2015-07-13 16:27:40 +08:00

弱问链表的回文是个啥...

rcmerci

2015-07-13 16:39:01 +08:00

吓尿了。。看成O(1)time了。