题解 | #链表中环的入口结点#

1.暴力解法：找到环中的任一位置，然后遍历链表，找到第一个在环中的结点，这个结点就是入口结点 50ms

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode* fast = pHead;
        ListNode* slow = pHead;
        //如果没有环，则返回空指针
        if(fast == nullptr || fast->next == nullptr)
        {
            return nullptr;
        }
        while(fast && fast->next)
        {
            //如果没有环，则返回空指针
            if(fast->next->next == nullptr)
            {
                return nullptr;
            }
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow)
                break;
        }//循环完成后fast指向环中的某一结点
        //遍历链表，找到第一个在环中的结点，这个结点就是入口结点
        while(pHead)
        {
            int flag = 0;//标记
            ListNode* temp = fast;//记录fast的初始位置
            //如果pHead与fast不相等，则遍历环找寻pHead是否在环中
            while(pHead != fast)
            {
                fast = fast->next;
                //如果找了一圈也没有，则退出，并将标记置1
                if(fast == temp)
                {
                    flag = 1;
                    break;
                }
            }
            //如果pHead不在环中，则继续遍历下一个结点
            if(fast == temp && flag == 1)
                pHead = pHead->next;
            else //如果在，则说明找到了，退出循环
                break;
        }
        return pHead;
	}
}

2. 解题思路：参考官方解题思路，表头到相遇点的距离为x+y,环的大小为y+z,并且 x+y = n*(y+z),所以环入口x = n*(y+z)-y，y为环入口到相遇点的距离。

当n=1时,x=z,z为相遇点到环入口的距离,当n = n时,x = n*环长+z

这样如果让一个指针从头开始遍历，一个指针从相遇点开始遍历，这样当它们再次相遇时，相遇点就是环的入口，因为环入口到相遇点的距离为y，这样当它绕n圈并+z以后，刚好就在环入口点

6ms

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        //如果为空链表，则返回空
        if(!pHead)
            return nullptr;
        ListNode* fast = pHead;
        ListNode* slow = pHead;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow)
            {
                //重新让slow从头开始走
                slow = pHead;
                //相遇时停止
                while(slow != fast)
                {
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }
        return nullptr;//如果没有环，则返回空指针
	}
}

3. 解题思路2：哈希法，使用集合set

1. 遍历单链表的每个结点
2. 如果当前结点地址没有出现在set中，则存入set中
3. 否则，出现在set中，则当前结点就是环的入口结点
4. 整个单链表遍历完，若没出现在set中，则不存在环

8ms

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        set<ListNode*> set;
        while(pHead)
        {
            if(set.find(pHead) == set.end())
            {
                set.insert(pHead);
                pHead = pHead->next;
            }
            else
                return pHead;
        }
        return nullptr;
	}
}