由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 如何在一个有cycle的linkedlist里search?
相关主题
一算法面试题我又fail了面试
链表中每三个数逆转的题?发几个狗家onsite题
面试面试官错了怎么办?问一道二叉树遍历的问题? 谢谢!
再回首,还是对linkedlist找cycle那题很疑惑LC的BST iterator到底要考察什么?
在版上看到的G题Linked List Cycle II好的算法
过不了leetcode Zigzag Level Order Traversalhow to judge a linked list is palindrome?
其实马工面试考coding也就是这5,6年的事情share一个大公司的onsite interview question
Binary Tree Level Order Traversal为什么老通不过关于BST traverse的复杂度
相关话题的讨论汇总
话题: cycle话题: linkedlist话题: search话题: node话题: 如何
进入JobHunting版参与讨论
1 (共1页)
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)

1 (共1页)
进入JobHunting版参与讨论
相关主题
关于BST traverse的复杂度在版上看到的G题
leetcode中的binary tree level order traverse II总是有run t过不了leetcode Zigzag Level Order Traversal
M家onsite题一道其实马工面试考coding也就是这5,6年的事情
再来一个design的题Binary Tree Level Order Traversal为什么老通不过
一算法面试题我又fail了面试
链表中每三个数逆转的题?发几个狗家onsite题
面试面试官错了怎么办?问一道二叉树遍历的问题? 谢谢!
再回首,还是对linkedlist找cycle那题很疑惑LC的BST iterator到底要考察什么?
相关话题的讨论汇总
话题: cycle话题: linkedlist话题: search话题: node话题: 如何