#pragmaonce#include<iostream>usingnamespacestd;template<classT>structLinkNode{T_data;LinkNode*_next;LinkNode(constT&x):_data(x),_next(NULL){}};template<classT>classListNode{//为了安全性private:ListNode(constListNode&l){}ListNode<T>&operator=(ListNodel){}public://程序限制LinkNode<T>*_head;public:ListNode():_head(NULL){}~ListNode(){while(_head){PopBack();}}voidPushBack(constT&x){LinkNode<T>*tmp=newLinkNode<T>(x);if(_head==NULL)_head=tmp;else{LinkNode<T>*cur=_head;while(cur->_next)cur=cur->_next;cur->_next=tmp;}}voidPopBack(){if(_head==NULL)return;if(_head->_next==NULL){delete_head;_head=NULL;}else{LinkNode<T>*cur=_head;while(cur->_next&&cur->_next->_next){cur=cur->_next;}LinkNode<T>*del=cur->_next;cur->_next=NULL;deletedel;}}LinkNode<T>*Search(constT&x){if(_head==NULL)returnNULL;LinkNode<T>*cur=_head;while(cur->_data!=x)cur=cur->_next;returncur;}};//判断链表是否带环template<typenameT>boolCheckIsCircle(LinkNode<T>*head){if(head==NULL||head->_next==NULL)returnfalse;LinkNode<T>*fast,*slow;fast=slow=head;while(fast&&fast->_next){fast=fast->_next->_next;slow=slow->_next;if(fast==slow)returntrue;}returnfalse;}template<classT>LinkNode<T>*SearchCircleAccess(LinkNode<T>*head){if(head==NULL||head->_next==NULL)returnNULL;LinkNode<T>*fast=head;LinkNode<T>*slow=head;while(fast&&fast->_next){fast=fast->_next->_next;slow=slow->_next;if(fast==slow)break;}slow=head;//于是我们从链表头、与相遇点分别设一个指针，//每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。//一个从头走，另一个从相遇点开始在环里走，//快指针比慢指针少走x,当它们相遇的第一个节点就是入口点while(slow!=fast){slow=slow->_next;fast=fast->_next;}returnslow;}voidTest1(){ListNode<int>l1;l1.PushBack(1);l1.PushBack(2);l1.PushBack(3);l1.PushBack(4);l1.PushBack(5);l1.PushBack(6);l1.PushBack(7);l1.PushBack(8);l1.PushBack(9);(l1.Search(9))->_next=l1.Search(6);//构建环if(CheckIsCircle(l1._head)){cout<<(SearchCircleAccess(l1._head))->_data<<endl;}}

运行结果：找到的入口点的数据为6