https://leetcode.com/problems/palindrome-linked-list/
我怎么觉得不能... 各位学过算法的球指点...
1
IwfWcf 2015-07-13 01:28:50 +08:00
可以做到,只是比较麻烦……
第一次遍历得到长度,确定中点;第二次遍历将中点之前的 list reverse,然后进行比较;第三次遍历将中点之前的 list 再次 reverse,恢复原始 list |
2
qw7692336 2015-07-13 01:48:17 +08:00
创建多一条出来。
|
4
Andiry 2015-07-13 02:03:12 +08:00 2
严格意义上不可能。任何需要修改原始输入的解法(比如原地reverse list)都不能算是O(1)空间复杂度。
|
5
20015jjw OP @IwfWcf reverse就需要存储关于n变大二变大的数据啊... 不管是弄个pointer往前指 还是把数据存在外部结构里...
|
6
sumhat 2015-07-13 03:01:46 +08:00
如果递归不算额外空间的话,也是可以的。
|
8
zhyu 2015-07-13 07:08:58 +08:00 via iPhone
|
9
wy315700 2015-07-13 07:46:51 +08:00
很简单啊
在操场上,两个人跑步,如果两个人速度不一样,那么,最终快的那个人会整整比慢的那个人快一圈的。 俗称套圈。 所以,弄两个指针,一个一次前进一步,一个一次前进两步,如果他们最终相遇了,那么就是存在环,否则就没有。 2011年银联面试题考过。 |
10
wy315700 2015-07-13 07:48:19 +08:00
不对,看错题了,无视我吧
|
11
20015jjw OP @zhyu 一个linkedlist如果有10000个link,需要10000个额外的pointers,然而如果只有1个,那就只需要一个额外的pointers,这不就是O(n) space么....
|
13
xcv58 2015-07-13 09:56:49 +08:00
1L 正解
这题相当无聊。 |
14
20015jjw OP @alafeizai 不懂... 我说的情况里长度为1和长度为10000的list需要的缓存一样多么?如果一样多,请问怎么实现呢?
|
15
yangff 2015-07-13 10:20:05 +08:00 via Android
不要慌。。上hash
|
16
20015jjw OP @20015jjw
好吧现在懂了 reverse list的时候只是用了原来的pointer 唯一需要增加的只是指向中点的pointer... 但是还是有点虚... 因为上午问大神大神说算法课学过palindrome问题不能是O(1) space |
17
IwfWcf 2015-07-13 10:33:55 +08:00
|
19
zhyu 2015-07-13 11:27:13 +08:00
|
22
IwfWcf 2015-07-13 15:29:37 +08:00
@zhyu 找不出来了,当时也没有特别记录,和这题类似最后 return bool,但我改了传入的 vector 的内容就被判错
|
23
ffffwh 2015-07-13 16:27:40 +08:00
弱问链表的回文是个啥...
|
24
rcmerci 2015-07-13 16:39:01 +08:00
吓尿了。。看成O(1)time了。
|