h**o
发帖数: 548 | 1 看了下网上答案五花八门，觉得没一个对的。
例如：http://stackoverflow.com/questions/5607292/interview-remove-loop-in-linked-list-java
1。if (fast_ptr==slow_ptr || fast_ptr->_next == slow_ptr)
应该改成 if (fast_ptr==slow_ptr)
2。应该检查 进入点是head的情况。可网上没一个检查的。为什么哪？
所以我的实现是这样的。 请大侠们帮看一下，或者给个正确答案的连接。
bool determine_remove_Cycle_list(sIntElement *head){
if (!head || !(head->_next)) return false;
sIntElement* slow_ptr = head;
sIntElement* fast_ptr = head;
while(true){
if (!fast_ptr || !(fast_ptr->_next)) return false;
slow_ptr = slow_ptr->_next;
fast_ptr = fast_ptr->_next->_next;
if (fast_ptr==slow_ptr)//do not check fast_ptr->_next == slow_ptr
break; //is cycle
}
fast_ptr = head;
while(fast_ptr->_next != slow_ptr->_next){
fast_ptr = fast_ptr->_next;
slow_ptr = slow_ptr->_next;
}
if (slow_ptr == head){ //special case: start of the cycle is head,
while (slow_ptr->_next != head){
slow_ptr = slow_ptr->_next;
}
}
slow_ptr->_next = NULL; //slow is the node before the start point
return true;
} |
c*********e
发帖数: 16335 | 2 妈呀，你在上 数据结构 吗？
【在 h**o 的大作中提到】
: 看了下网上答案五花八门，觉得没一个对的。
: 例如：http://stackoverflow.com/questions/5607292/interview-remove-loop-in-linked-list-java
: 1。if (fast_ptr==slow_ptr || fast_ptr->_next == slow_ptr)
: 应该改成 if (fast_ptr==slow_ptr)
: 2。应该检查 进入点是head的情况。可网上没一个检查的。为什么哪？
: 所以我的实现是这样的。 请大侠们帮看一下，或者给个正确答案的连接。
: bool determine_remove_Cycle_list(sIntElement *head){
: if (!head || !(head->_next)) return false;
: sIntElement* slow_ptr = head;
: sIntElement* fast_ptr = head;
|
c*********e
发帖数: 16335 | 3 加几个断点调试啊。在while loop后加个断点，感觉程序在while loop里结束了，不会
到while loop 后面去。
【在 h**o 的大作中提到】
: 看了下网上答案五花八门，觉得没一个对的。
: 例如：http://stackoverflow.com/questions/5607292/interview-remove-loop-in-linked-list-java
: 1。if (fast_ptr==slow_ptr || fast_ptr->_next == slow_ptr)
: 应该改成 if (fast_ptr==slow_ptr)
: 2。应该检查 进入点是head的情况。可网上没一个检查的。为什么哪？
: 所以我的实现是这样的。 请大侠们帮看一下，或者给个正确答案的连接。
: bool determine_remove_Cycle_list(sIntElement *head){
: if (!head || !(head->_next)) return false;
: sIntElement* slow_ptr = head;
: sIntElement* fast_ptr = head;
|
h**o
发帖数: 548 | 4 为什么妈啊？这不是面试经典题吗?
我调了两个例子：1->2->3->4->1 和 1->2->3->4->2. 结果我的程序是对的，
但我就是不确信，难道别人都不对 就我对了？还是我漏了什么？
【在 c*********e 的大作中提到】
: 加几个断点调试啊。在while loop后加个断点，感觉程序在while loop里结束了，不会
: 到while loop 后面去。
|
k********4
发帖数: 858 | |
k********4
发帖数: 858 | 6 if (slow_ptr == head){ //special case: start of the cycle is head,
while (slow_ptr->_next != head){
slow_ptr = slow_ptr->_next;
}
}
这段干嘛的，看不懂，好像完全没影响返回值啊 |
h**o
发帖数: 548 | 7 while(fast_ptr->_next != slow_ptr->_next)这个loop 是为了求 循环链 的入口。
即：若 1->2->3->4->2, 入口是2， 当这个loop结束时 slow 应该为4， slow->next应
该为2.
所以改slow->next=NULL就可以把循环去掉。
但如果开始while(fast_ptr->_next != slow_ptr->_next)这个loop 前slow就是head,
这个while loop 不会执行。(这种情况出现在循环链 的入口 是head.即：1->2->3->4-
>1, 入口是1) 如果 直接令slow->next=NULL 是不对的。那样就得结果 head=1->
null 而非 head->1->2->3->4->null 了。
【在 k********4 的大作中提到】
: if (slow_ptr == head){ //special case: start of the cycle is head,
: while (slow_ptr->_next != head){
: slow_ptr = slow_ptr->_next;
: }
: }
: 这段干嘛的，看不懂，好像完全没影响返回值啊
|
