|
锁定老帖子 主题：如何检测循环链表
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-08-29
如何检测循环链表
声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2011-08-29
用个hash table把以前走过的节点都记下来。如果是面试题，另当别论。。。
|
| 返回顶楼 | |
|
发表时间：2011-09-26
public interface Node {
public Node next();
public boolean hasNext();
}
public static boolean hasLoop(Node root) {
ArrayList<Node> list = new ArrayList<Node>();
Node node = root;
while (node.hasNext()) {
list.add(node);
node = node.next();
if (contains(list, node))
return true;
}
return false;
}
private static <E> boolean contains(List<E> list, E elem) {
Iterator<E> iter = list.iterator();
while (iter.hasNext()) {
E e = iter.next();
if (e == elem)
return true;
}
return false;
}
先保证正确性，待改进。。。。 |
| 返回顶楼 | |
|
发表时间：2011-09-26
chen_yongkai 写道
public interface Node {
public Node next();
public boolean hasNext();
}
public static boolean hasLoop(Node root) {
ArrayList<Node> list = new ArrayList<Node>();
Node node = root;
while (node.hasNext()) {
list.add(node);
node = node.next();
if (contains(list, node))
return true;
}
return false;
}
private static <E> boolean contains(List<E> list, E elem) {
Iterator<E> iter = list.iterator();
while (iter.hasNext()) {
E e = iter.next();
if (e == elem)
return true;
}
return false;
}
先保证正确性，待改进。。。。
public static boolean hasLoop(Node root) {
r1 = root.clone();
r2 = root.clone();
while(true){
if(r1.hashnext){r1 = r1.next();}else{break;}
if(r1.hashnext){r1 = r1.next();}else{break;}
if(r2.hashnext){r2 = r2.next();}else{break;}
if(r1 == r2 ) return true;
}
return false;
}
|
| 返回顶楼 | |
|
发表时间：2011-09-28
... 好歹用个hash table吧，不然复杂度还不如抛那个经典面试解法呢⋯⋯
话说为啥要clone啊？ |
| 返回顶楼 | |
|
发表时间：2011-09-28
cat 写道 ... 好歹用个hash table吧，不然复杂度还不如抛那个经典面试解法呢⋯⋯
话说为啥要clone啊？ 传进来的带引用的东西如果会改变状态就有种想想clone的强迫症 例如：传入一个itrater |
| 返回顶楼 | |
|
发表时间：2011-09-29
你就不怕clone给你来个deep copy, 然后r1永远!= r2啊~
|
| 返回顶楼 | |
|
发表时间：2011-09-29
cat 写道 你就不怕clone给你来个deep copy, 然后r1永远!= r2啊~
是啊很有可能的。。。。。。 那最后一个if应该用r1.isSame（r2）; 才合适啊 |
| 返回顶楼 | |
|
发表时间：2011-11-04
用两个指针,同时从链表的头开始走.一个指针没次移动一个节点.另一个每次移动两个节点..
1.当某个时刻,两个节点指向同一个节点时,则是循环链表. 2.当移动快的节点走到尾节点时,则不存在. |
| 返回顶楼 | |
|
发表时间：2011-11-04
这个问题，必须要求链表中的每一个节点有个唯一性的标识，要不如果中间有一段链接片段重复几次的话，就不能判断循环了。
在生成链表时每个链表节点中设置一个当前节点通过链表头遍历过来的节点个数当做唯一性标识。 这样判断链表循环，只需要遍历链表，当链表的下一个节点的标识位不是上一个节点的标识位+1 就可以断定链表中出现了循环 |
| 返回顶楼 | |
