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倍，快指针路程-慢指针路程=环大小。

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。