题目描述

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

数据范围：n≤10000，1<=结点值<=10000
要求：空间复杂度 O(1)，时间复杂度O(n)

例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示：

题解1：使用set容器

代码

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        set<ListNode*> s;
        while(pHead){
            if(s.find(pHead) == s.end()){//未查找到
                s.insert(pHead);//则将不重复的元素放入set容器中
                pHead = pHead->next;//指针向下移动
            }
            else
                return pHead;//找到重复元素，返回该结点
        }
        return pHead;//若不存在环，则返回NULL
    }
};

题解2：快慢指针

用快慢指针可以很容易判断一条链表是否存在环，快指针fast每次走两步，慢指针slow每次走一步，那么若进入环中，每次他们之间的相对距离都会-1，直到两者相遇。
假设从头节点到环的入口节点的前一个节点一共有a个，环中的节点有b个，
设fast指针走过的节点数是f,slow指针走过的节点数是s，那么有以下两个结论：
f = 2 * s （即快指针走过的节点数一定是慢指针的两倍）
f = s + nb （当两者相遇时，快指针一定已经绕环走了n圈）
由上面两个等式可以得出，f = 2nb，s = nb

算法步骤为：

在快慢指针第一次相遇前，快指针每次走两步，慢指针每次走一步 快慢指针相遇之后，快慢指针都每次仅走一步，直到再次相遇时，那个位置的结点就是环的入口结点

代码

ListNode* EntryNodeOfLoop2(ListNode* pHead) {
    ListNode* fast = pHead;
    ListNode* slow = pHead;
    while (fast)
    {
        slow = slow->next;//慢指针仅走一步
        if (fast->next == NULL) return NULL;
        fast = fast->next->next;//快指针走两步
        if (fast == slow) {//两个指针走到环形节点的同一个节点处，slow走了nb步
            fast = pHead;//快指针重新移动到头部
            while (fast !=slow)
            {//两个指针相遇，fast指向头指针之后，fast和slow每次都向后移动一步
                fast = fast->next;
                slow = slow->next;
            }//当再次相遇时候，就是环形节点的入口位置
            return fast;
        }
    }
    return NULL;
}