怎样除去循环链 - JobHunting版

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

JobHunting版 - 怎样除去循环链

相关主题
● 请问大牛们Leetcode Reorder List 中找中间节点怎么能现场想清楚？多谢！	● 谁能帮我看下insertion sort list这道题吗？
● 一到电面题	● 删除node从list, 这个有内存泄露么，怎么释放内存，对于那个被删除的节点？
● 【我自己写的LinkedList为什么总有错?】	● google面试全过程(简装版)
● ms面试题目	● copy link with random additional pointers
● Programming interview exposed 上面的那道NULL or Cycle的linked list题	● M家 onsite 悲剧，同胞们弄死烙印吧
● 大牛们帮忙，Rverse Nodes in k-Group	● yelp 面经
● delete a node in linked list	● 合并两个排序好的链表, 优解?
● LeetCode:Partition List 哪位帮我看看，为什么总是TLE	● 如何删除 linked list 的最后一个元素 (转载)

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

进入JobHunting版参与讨论

(共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页)

进入JobHunting版参与讨论

相关主题
● 如何删除 linked list 的最后一个元素 (转载)	● Programming interview exposed 上面的那道NULL or Cycle的linked list题
● Populating Next Right Pointers in Each Node II	● 大牛们帮忙，Rverse Nodes in k-Group
● leetcode populating next pointer 2	● delete a node in linked list
● 哪位大侠帮我看看这个code	● LeetCode:Partition List 哪位帮我看看，为什么总是TLE
● 请问大牛们Leetcode Reorder List 中找中间节点怎么能现场想清楚？多谢！	● 谁能帮我看下insertion sort list这道题吗？
● 一到电面题	● 删除node从list, 这个有内存泄露么，怎么释放内存，对于那个被删除的节点？
● 【我自己写的LinkedList为什么总有错?】	● google面试全过程(简装版)
● ms面试题目	● copy link with random additional pointers

相关话题的讨论汇总
话题: 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日

历史上的今天