判断链表是否带环，若带环，找到环的入口点

#pragma once #include<iostream> using namespace std; template<class T> struct LinkNode {	T _data;	LinkNode* _next;	LinkNode(const T& x)	:_data(x)	, _next(NULL)	{} }; template<class T> class ListNode {	//为了安全性 private:	ListNode(const ListNode& l)	{}	ListNode<T>& operator=(ListNode l)	{} public:	//程序限制	LinkNode<T>* _head; public:	ListNode()	:_head(NULL)	{}	~ListNode()	{	while (_head)	{	PopBack();	}	}	void PushBack(const T& x)	{	LinkNode<T>* tmp = new  LinkNode<T>(x);	if (_head == NULL)	_head = tmp;	else	{	LinkNode<T>* cur = _head;	while (cur->_next)	cur = cur->_next;	cur->_next = tmp;	}	}	void PopBack()	{	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;	delete del;	}	}	LinkNode<T>* Search(const T& x)	{	if (_head == NULL)	return  NULL;	LinkNode<T>*  cur = _head;	while (cur->_data != x)	cur = cur->_next;	return cur;	} }; //判断链表是否带环 template<typename T> bool CheckIsCircle(LinkNode<T>* head) {	if (head == NULL || head->_next == NULL)	return false;	LinkNode<T>* fast, *slow;	fast = slow = head;	while (fast&&fast->_next)	{	fast = fast->_next->_next;	slow = slow->_next;	if (fast == slow)	return true;	}	return false; } template<class T> LinkNode<T>* SearchCircleAccess(LinkNode<T>* head) {	if (head == NULL||head->_next==NULL)	return NULL;	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;	}	return slow; } void Test1() {	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