C++单链表对环的操作。

#include <iostream>using namespace std;template<typename _Ty>class Node{public:Node(_Ty _X=_Ty()):_Data(_X),_Next(NULL){}int _Data;Node<_Ty> *_Next;};template<typename _Ty>class List{public:List(){_First = new Node<_Ty>();}void Insert(int _X){Node<_Ty> *_S = new Node<_Ty>(_X);_S->_Next = _First->_Next;_First->_Next = _S;}Node<_Ty>* IsCircle()//判断是否是环，并且返回第一次相遇节点地址{Node<_Ty> *_P= _First;Node<_Ty> *_Q= _First;while(_P!=NULL && _P->_Next!=NULL){_P=_P->_Next->_Next;_Q=_Q->_Next;if(_P==_Q)return _P;}return NULL;}void SetCircle(int _X)//设置环的位置。{Node<_Ty>* _P = _First;Node<_Ty>*_Q = _First;while(_Q->_Next!=NULL){_Q=_Q->_Next;}for(int _I=0;_I<_X;_I++){_P=_P->_Next;}_Q->_Next=_P;}int GetCircleLength()//找环的大小{Node<_Ty> *_P = _First;Node<_Ty> *_Q = _First;int _A=0;while(1){_P=_P->_Next->_Next;_Q=_Q->_Next;_A++;if(_P==_Q)break;}return 2*_A-_A;}int GetCircle()//得到环点到开始节点的节点个数.。{Node<_Ty> *_P = IsCircle();Node<_Ty> *_Q = _First;int _A=0;while(_P!=_Q){_P=_P->_Next;_Q=_Q->_Next;_A++;}return _A;}/*void Show(){Node<_Ty> *_P = _First;while(_P->_Next!=NULL){cout<<_P->_Next->_Data<<" ";_P=_P->_Next;}cout<<endl;}*/private:Node<_Ty> *_First;};int main(){List<int> list;for(int i=0;i<20;i++){list.Insert(i);}list.SetCircle(10);//设置环的位置if(list.IsCircle()){cout<<"有环！"<<endl;}else{cout<<"无环"<<endl;} cout<<"环的位置是:"<<list.GetCircle()<<endl; cout<<"环的长度是:"<<list.GetCircleLength()<<endl; return 0;}

感想：1.判断是否有环用快慢指针。

2.当第一次相遇之后，快指针改变速度从一次走两个节点变成一个节点，慢指针从头开始走，当他们再次相遇时的节点就是环开始位置。

3.环的长度就是第一次快慢指针相遇时慢指针所走过的节点数，因为快指针速度是慢指针的2倍，快指针路程-慢指针路程=环大小。

，强者能同命运的风暴抗争。