Here is my algorithm:1: Delete all the duplicated elements in this linked nodes. 2: Create a Set and an int variable count. 3: Starting from the head node, go through the whole nodes, add every node to the Set and count ++. if count > the size of the Set. That means it's a 循环链表.
Zen me biao ji a? Ru guo you chong fu de ne?
Firstly, to delete all the duplicated nodes, and add this method. That's better.
1-2-3-4-5-6-7-2* // 2* means 7.next = 2; If no duplication, you know 2 is unique.1-2-3-2-5-6-2-6-2* // In this situation, you don't know whetehr 6-2 is the cycle, or 2 is 6.next.
不需要删除重复的node,比较的时候只要比较指针地址或者引用是否相等就行了,管它里面存的值是多少
LList l = ...; //这个是给定的链表 boolean circleHappened = false; // 这个保存结果 LNode n = l.getHeader(); LNode sn = n; //先标记一个节点 do { n = n.next(); sn = sn.next(); if(sn == null) break; //遍历完了,没有环 sn = sn.next(); if(sn == n) { // 遍历回来了说明有环; 注意这里用的是== circleHappened = true; break; }
如果链表是一个对象,这就很好办,出现这种情况的时候修改对象的属性,就不需要遍历,根据属性来判断就可以了。如果链表不是一个对象,而只是一个概念,这个链表是多个对象自串联起来的,那么,在对象里面增加一个属性checked
1.设置checkValue的值为当前时间(毫秒)
2.选择链表的任意一个点开始检测
3.判断checked的值是否为checkValue,如果是,则为循环链表,检测结束。
如果不是,设置checked的值为checkValue。
4.找到下一个点,如果没有下一个点,则不是循环链表,检测结束。
如果有下一个点,重复3.
在对象中增加一个属性会增加内存消耗!
If there are duplicated elements, it's not so easy...
一个指针一次next,另外一个遍历next->next,如果发生循环,就可判断了
2: Create a Set and an int variable count.
3: Starting from the head node, go through the whole nodes, add every node to the Set and count ++. if count > the size of the Set. That means it's a 循环链表.
第三条中,checked的值为什么会等于checkValue的值呢?
在对象中增加一个属性会增加内存消耗!
[/Quote]因为第三条后半句说了,如果checked值不为checkValue的值,则设置checked=checkValue。
这里相当于对检测过的节点添加标志,本来直接用true和false来标志就可以了,设置为当前时间是为了同时标志检测时间点。内存消耗问题,增加这么一个属性,10万条数据,内存也不会增加超过1M,完全能够接受。
每查找一次都要遍历一次?这样要花不少时间!
貌似很简单,两个指针A,B,A指针不动,B指针移动,初始值B=A->next,当A=B时,形成环,否则B->next==null时不形成环
1.设置checkValue的值为当前时间(毫秒)
这个值是当前时间怎么可能会和第3条中的中的checkedValue的值相等,因为你checkValue是当前时间值,而checked的值是上一次checkValue的值!
谢谢,请再赐教!
1.设置checkValue的值为当前时间(毫秒)
这个值是当前时间怎么可能会和第3条中的中的checked的值相等,因为你checkValue是当前时间值,而checked的值是上一次checkValue的值!
然后再遍历的时候没遍历一个节点都判断该节点的next节点是否等于front,如果等于,表示成环了
这里的等于表示地址等于
LList l = ...; //这个是给定的链表
boolean circleHappened = false; // 这个保存结果
LNode n = l.getHeader(); LNode sn = n; //先标记一个节点
do {
n = n.next();
sn = sn.next();
if(sn == null) break; //遍历完了,没有环
sn = sn.next();
if(sn == n) { // 遍历回来了说明有环; 注意这里用的是==
circleHappened = true;
break;
}
} while(sn != null);//遍历完了,没有环return circleHappened;
貌似这个某大企业的经典题目
n = n.next();//n为什么也要移动???
sn = sn.next();
if(sn == null) break;
sn = sn.next();
if(sn == n) {
circleHappened = true;
break;
}
} while(sn != null);
http://hi.baidu.com/leaf82318/blog/item/73d8bbd64f10342a07088bad.html
进行一次遍历查找,判断尾节点的next指针值,是否与链表中(包括头节点)的next指针值相同。