怎样除去循环链 - CS版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

CS版 - 怎样除去循环链

相关主题
● 请教方向选择，真心求建议	● 问graph问题
● 硬盘速度	● 各位大哥知道Dos下怎么截图么
● 请问一个图的分解问题	● opengl里怎么固定一个window的尺寸？
● How to find all cycles in a directed graph?	● C++（非VC++）删除链表时如何对指针操作? 在线等回复！谢谢！
● Re: How to find all cycles in a directed	● 请问strcpy()和memcpy()的写法问题
● 为什么多个线程生成的随机数是一样的？	● Deloitte德勤校园初面求教包子酬谢！！
● how to delete a file with NULL name in unix? (转载)	● 问一个很简单的编程问题
● 问个common lisp的问题	● 问一个C++的binary search tree类实现问题 (转载)

相关话题的讨论汇总
话题: ptr话题: slow话题: fast话题: next话题: head

进入CS版参与讨论

(共1页)

h**o
发帖数: 548

看了下网上答案五花八门，觉得没一个对的。
例如：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;
}

(共1页)

进入CS版参与讨论

相关主题
● 问一个C++的binary search tree类实现问题 (转载)	● Re: How to find all cycles in a directed
● 新手问个MIPS 问题	● 为什么多个线程生成的随机数是一样的？
● c++类未完成初始化，如何引用this?	● how to delete a file with NULL name in unix? (转载)
● 请教一下，我还要继续做科研不	● 问个common lisp的问题
● 请教方向选择，真心求建议	● 问graph问题
● 硬盘速度	● 各位大哥知道Dos下怎么截图么
● 请问一个图的分解问题	● opengl里怎么固定一个window的尺寸？
● How to find all cycles in a directed graph?	● C++（非VC++）删除链表时如何对指针操作? 在线等回复！谢谢！

相关话题的讨论汇总
话题: ptr话题: slow话题: fast话题: next话题: head

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

boards

未名新帖统计// 7月16日

历史上的今天