【题解】判断链表中是否有环、链表中环的入口结点

判断链表中是否有环

题目链接：判断链表中是否有环

解题思路1：快慢指针

代码如下：

    bool hasCycle(ListNode *head) {if(head == nullptr) return false;ListNode* fast = head;ListNode* slow = head;while(fast!=nullptr && fast->next != nullptr){fast = fast->next->next;slow = slow->next;if(fast == slow){return true;}}return false;}

解题思路2：hash法

我们把所有的节点放到哈希表中，我们遍历整个链表，如果存在重复的相同节点，那就证明链表中有环

代码如下：

    bool hasCycle(ListNode *head) {map<ListNode*, int> mp;ListNode* cur = head;while(cur != nullptr){if(mp[cur] == 1) return true;mp[cur] = 1;cur = cur->next;}return false;}

链表中环的入口结点

题目链接：链表中环的入口结点

解题思路1：hash法，记录第一次重复的节点

代码如下：

    ListNode* EntryNodeOfLoop(ListNode* pHead) {map<ListNode*, int> mp;ListNode* cur = pHead;while (cur != nullptr) {if (mp[cur] == 1) return cur;mp[cur] = 1;cur = cur->next;}return nullptr;}

解题思路2：快慢指针

上面我们用快慢指针来判断一个链表是否有环，我们也可以通过快慢指针来找到环的入口节点。我们要找到快慢指针之间步数的数学关系，借助数学关系来找到环的入口节点
假设从头结点到环的入口节点一共有a个节点，环中的节点一共有b个，设快指针走的步数为f，慢指针走的步数为s，那么有步数之间有这样的数学关系：

• f = 2 * s ；快指针一次走两步，慢指针一次走一步
• f = s + nb ；当快慢指针相遇时，快指针一定比慢指针多走了nb步，意思就是多绕环了n圈

所以可以得出：s = nb，f = 2nb；

当快慢指针相遇时，慢指针已经走了nb步，快指针走了2nb步，同时我们要走到环的入口节点需要走a + kb 步，而这时慢指针的nb只要再走a步即可到达入口，所以我们把快指针移动到头节点，之后，再让两个指针一次走一步往前走，当他们相遇时所处的节点就是入口节点

代码如下：

    ListNode* EntryNodeOfLoop(ListNode* pHead) {ListNode* fast = pHead;ListNode* slow = pHead;while(fast != nullptr){slow = slow->next;if(fast->next == nullptr) return nullptr;//链表中无环fast = fast->next->next;if(fast == slow){//快慢指针相遇fast = pHead;//让快指针重新指向pHeadwhile(fast != slow){//通过两个指针的相遇，控制fast走a步fast = fast->next;slow = slow->next;}return fast;//此时fast即是入口节点，直接返回}}return nullptr;}