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;  
}  </pre> 



 感想：1.判斷是否有環用快慢指針。 

            2.當第一次相遇之后，快指針改變速度從一次走兩個節點變成一個節點，慢指針從頭開始走，當他們再次相遇時的節點就是環開始位置。 
            3.環的長度就是第一次快慢指針相遇時慢指針所走過的節點數，因為快指針速度是慢指針的2倍，快指針路程-慢指針路程=環大小。