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

            返回值描述：

返回链表的环的入口结点即可。而我们后台程序会打印这个节点。

简述

        给定链表的头结点，若有环则找到链表的入环节点。

算法一 : 哈希表

    时间复杂度：O(N)

    思路：

        从头开始将每个节点存入哈希表中，如果第一次遇到该节点已经在哈希表中那么该节点为入口节点。如果链表能被遍历完，说明不存在环，则返回NULL。

        原因：1. 链表中每个节点的地址是不一样的，那么我们分别将这些地址存进哈希表中，如果该节点已经在哈希表中，那么说明我走了重复的路。

                   2. 对于重复的路那么肯定是环的节点，而入口节点也是环的一个节点，也是被存入哈希表中的第一个环的节点。

    图解：

        

    代码:

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    unordered_set<ListNode*> hash;
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if(pHead){
            ListNode* t=pHead;
            if(hash.find(t)==hash.end()){
                hash.insert(t);
                if(pHead->next) return EntryNodeOfLoop(pHead->next);
            }
            else return t;
        }
        return NULL;
    }
};

算法二 : 双指针

    时间复杂度：O（N）

    思路:

            1. 利用两个指针，快指针 j ，慢指针 i 。j 的速度是 i 的两倍，让他们不断往后走，直到两者相遇为止。

            2. 让 j 回到头结点 ，然后再让 j 和 i 以相同速度走，i 与 j 再次相遇的点即为入口节点。

            具体证明如图所示

    图解：

    代码:

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if(!pHead) return NULL;
        ListNode* i=pHead;
        ListNode* j=pHead;
        while(j&&j->next){
            i=i->next;
            j=j->next->next;
            if(i==j) break;
        }
        if(!j||!j->next) return NULL;
        j=pHead;
        while(j!=i){
            i=i->next;
            j=j->next;
        }
        return j;
    }
};