判断链表是否有环以及环的入口点(转载) 留个记号
有几种解法：
1. 遍历链表，将已经遍历过的节点放在一个hash表中，如果一个节点已经存在hash表中，说明有环。时间:O(n) 空间:O(n)
2. 反转链表 时间O(n)，空间O(1),使用三个指针
3. 快慢指针。 时间O(n), 空间O(1),使用两个指针
参考：
http://kb.cnblogs.com/page/52054/
http://www.cnblogs.com/shawn-zhou/archive/2008/11/26/1341307.html
http://kb.cnblogs.com/page/52054/
[url]http://keep.javaeye.com/blog/293454 [/url]
【摘要】有一个单链表，其中可能有一个环，也就是某个节点的next指向的是链表中在它之前的节点，这样在链表的尾部形成一环。1、如何判断一 个链表是不是这类链表？2、如果链表为存在环，如果找到环的入口点？扩展：判断两个单链表是否相交，如果相交，给出相交的第一个点。
有一个单链表，其中可能有一个环，也就是某个节点的next指向的是链表中在它之前的节点，这样在链表的尾部形成一环。
问题：
1、如何判断一个链表是不是这类链表？
2、如果链表为存在环，如果找到环的入口点？
解答：
一、判断链表是否存在环，办法为：
设置两个指针(fast, slow)，初始值都指向头，slow每次前进一步，fast每次前进二步，如果链表存在环，则fast必定先进入环，而slow后进入环，两个指针必定相遇。(当然，fast先行头到尾部为NULL，则为无环链表)程序如下：
bool IsExitsLoop(slist * head){slist * slow = head , * fast = head; while ( fast && fast -> next ) {slow = slow -> next;fast = fast -> next -> next;if ( slow == fast ) break ;} return ! (fast == NULL || fast -> next == NULL);} slist * FindLoopPort(slist * head){slist * slow = head, * fast = head; while ( fast && fast -> next ) {slow = slow -> next;fast = fast -> next -> next;if ( slow == fast ) break ;} if (fast == NULL || fast -> next == NULL) return NULL;slow = head; while (slow != fast){slow = slow -> next;fast = fast -> next;} return slow;}