g*******s
发帖数: 2963 | 1 n 个 node的list
我能想到的是用传统找cycle的方法，但这需要两个指针。而且当两个指针重合的时候
已经多traverse了不少 (steps > n)。
另外一种方法就是hash traverse过的node pointer，发现hash过的停止搜索
想知道有没有不用extra space并且指遍历一遍的 （steps = n） |
d**e
发帖数: 6098 | 2 我觉得应该没有，如果有的话，反证法，找cycle就不用一快一慢指针了。
【在 g*******s 的大作中提到】
: n 个 node的list
: 我能想到的是用传统找cycle的方法，但这需要两个指针。而且当两个指针重合的时候
: 已经多traverse了不少 (steps > n)。
: 另外一种方法就是hash traverse过的node pointer，发现hash过的停止搜索
: 想知道有没有不用extra space并且指遍历一遍的 （steps = n）
|
s*****n
发帖数: 5488 | 3 写个递归程序或者loop
1. foreach node p
comp value
p->next = p->prev;
if there is a cycle in the ll, you will reach the head node eventually when
there is no search result found.
2. start from here, reverse eveything again to restore the linkedlist.
【在 g*******s 的大作中提到】
: n 个 node的list
: 我能想到的是用传统找cycle的方法，但这需要两个指针。而且当两个指针重合的时候
: 已经多traverse了不少 (steps > n)。
: 另外一种方法就是hash traverse过的node pointer，发现hash过的停止搜索
: 想知道有没有不用extra space并且指遍历一遍的 （steps = n）
|
