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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
#include <set>
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        set<ListNode*> st;
        set<ListNode*>::iterator iter;
        while (pHead) {
            if ((iter = st.find(pHead))!=st.end()) {
                return pHead;
            }
            st.insert(pHead);
            pHead=pHead->next;
        }
        return nullptr;
    }
};

第一种方法使用哈希表实现，每次遍历一个结点都判断是否已存在哈希表中，如果是则说明有环，如果不在里面则添加进去即可。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode* slow=pHead;
        ListNode* fast=pHead;
	  //注意快指针跑的快，所以以它和下个结点是否为空为循环结束条件
        while(fast && fast->next){
            fast=fast->next->next;
            slow=slow->next;
		  //两指针相遇
            if(slow==fast){
                break;
            }
        }
	  //若是以其中一个为空跳出的循环则不存在环
        if(fast==nullptr||fast->next==nullptr){
            return nullptr;
        }
	  //重新从头结点出发
        fast=pHead;
        while (fast!=slow) {
		  //快慢结点以相同的速度行进
            fast=fast->next;
            slow=slow->next;
        }
	  //相遇点fast==slow为环的入口点
        return fast; 
    }
};

第二种方法使用快慢指针实现，由于快指针的速度是慢指针的两倍，所以当存在环时二者相遇时，该位置与下次经过的入口点的距离是和从起始位置到入口点的距离是相等的，如下图所示，此时若是让快指针重新从头结点出发，以和慢结点相同的速度行走则相遇点即为环的入口点。