判断一个linked list是不是palindrome - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

判断一个linked list是不是palindrome

判断一个linked list是不是palindrome# JobHunting - 待字闺中

b*l2013-04-16 07:04

1 楼

在以下三种方法之外还有没有更好的方法？
1. 把半个linked list给reverse
2. 用stack存下一半
3. Recursion
有没有一种复杂度是O(n)且不用 extra linear storage的方法？

d*x2013-04-16 07:04

2 楼

第一种不就不用extra storage嘛

【在 b*******l 的大作中提到】

: 在以下三种方法之外还有没有更好的方法？
: 1. 把半个linked list给reverse
: 2. 用stack存下一半
: 3. Recursion
: 有没有一种复杂度是O(n)且不用 extra linear storage的方法？

z*22013-04-16 07:04

3 楼

doubly linked list

l*t2013-04-16 07:04

4 楼

recursion不是么
如果不算stack的话

【在 b*******l 的大作中提到】

b*l2013-04-16 07:04

5 楼

对，我的意思是说也不要改变linked list。不好意思，我没说清楚。
我想知道，还有没有更好的办法？如果没有的话，我觉得第二个办法，用stack相对来
说更简洁一些。

【在 d**********x 的大作中提到】

: 第一种不就不用extra storage嘛

b*l2013-04-16 07:04

6 楼

这个不行，必须是singly linked list。再加一个property代价太大了。

【在 z***2 的大作中提到】

: doubly linked list

b*l2013-04-16 07:04

7 楼

但是recursion本身就得用到stack啊。

【在 l*******t 的大作中提到】

: recursion不是么
: 如果不算stack的话

l*t2013-04-16 07:04

8 楼

我知道，但大家很多时候不把stack当space要求的吧？

【在 b*******l 的大作中提到】

: 但是recursion本身就得用到stack啊。

b*l2013-04-16 07:04

9 楼

对。但是recursion本身确实要用很多的memory。这个是我刚在网上看到的：
ADVANTAGES AND DISADVANTAGES OF RECURSION
Advantages
Although at most of the times a problem can be solved without recursion, but
in some situations in programming, it is a must to use recursion. For
example, a program to display a list of all files of the system cannot be
solved without recursion.
The recursion is very flexible in data structure like stacks, queues, linked
list and quick sort.
Using recursion, the length of the program can be reduced.
Disadvantages
It requires extra storage space. The recursive calls and automatic variables
are stored on the stack. For every recursive calls separate memory is
allocated to automatic variables with the same name.
If the programmer forgets to specify the exit condition in the recursive
function, the program will execute out of memory. In such a situation user
has to press Ctrl+ break to pause and stop the function.
The recursion function is not efficient in execution speed and time.
If possible, try to solve a problem with iteration instead of recursion.

【在 l*******t 的大作中提到】

: 我知道，但大家很多时候不把stack当space要求的吧？