【剑指】65，找到链表环的入口节点（进环，得数，一起走）

客官°小女子只卖身不卖艺 2023-07-14 15:55 53阅读 0赞

**题目描述**  
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。  
思路：  
1，快慢指针先将一个指针打入环内，  
2，计算环内有多少个节点  
3，从开开始让一个指针先走环内的节点数的节点，然后两个指针再一起走，最终相遇点就是环的入口点

代码：  
首先确定有环：

class Solution { 
    public:
        ListNode* EntryNodeOfLoop(ListNode* pHead)
        { 
    		if(pHead ==nullptr || pHead->next==nullptr)
                return nullptr;
            ListNode* left=pHead;
            ListNode* right=pHead->next->next;
            while(right!=left)
            { 
                right=right->next;
                    right=right->next;
                left=left->next;
            }
            //相遇了。通过让一个节点先走环数的步，再两个节点一起走，
            //意味着一个节点走完了整条链后到达环的入口处，另一个节点走了除环数的步数
            //计算环节数
            int count=1;
            ListNode* tmp=right->next;
                while(tmp!=right)    //错误在这里！tmp在后面，我用right走
                { 
                    tmp=tmp->next;
                    count++;
                }
            left=pHead,right=pHead;
            if(count>0)    //先走count步
                 for(int i=0;i<count;i++)
                     left=left->next;
            while(left!=right)
            { 
                left=left->next;
                right=right->next;
            }
            return right;
    	}
    }；