链表有无环以及确定入环口详解

142.环形链表 II

        给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

        如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1

输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0

输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1

输出：返回 null 解释：链表中没有环。

---

判断是否有环

---

算法思想：经典的快慢指针问题，设置快慢指针，slow 和 fast 初始时都指向链表的头结点 head，然后慢指针每次走一步，快指针每次走两步，这样快指针一定比慢指针先入环，经过不断的走下去，若是链表有环，快慢指针必会在环上相遇

#include<iostream>
#include<math.h>
using namespace std;
struct ListNode {int val;ListNode* next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode* next) : val(x), next(next) {}};bool hasCycle(ListNode* head) {if (head == nullptr || head->next == nullptr) return false;	// 链表没有元素或者只有一个元素ListNode* fast = head;ListNode* slow = head;while (fast != nullptr && fast->next != nullptr) {slow = slow->next;fast = fast->next->next;if (slow == fast) return true;}return false;}

---

判断入环口

---

        判断链表的入环口相当于判断两长度不一的链表的公共结点初始位置（长的先走两链表的差值，然后一起走），按道理我们应该让长的链表先走（假设长链表是初始链表，短链表是从环开始的链表），由于链表有环我们无法准确的知道链表的长度，那么如何判断入环口呢？

        首先我们应该知道，在 slow 入环的时候，fast 早已入环，那么 slow 和 fast 之间的距离必定小于环长，所以当 fast 和 slow 相遇的时候，slow 在环内走的距离一定小于环长。

        我们假设头结点距离入环口的长度为 a ，fast 和 slow 相遇的位置距离入环口 x ，环的长度为 r .那么由上图可知 slow 走的距离是 a+x，而由于相遇之前 fast 可能已经绕环 n 圈，那么 fast 所走的距离是 a + r*n + x，又由于 fast 所走的步长等于 slow 的两倍，所以 2*(a+x) = a + r*n + x => a = r*n - x。

再回到寻找两链表的公共结点，我们已经知道了链表长度的差值 a，又已知链表是有环的，那么不妨设 h1 = head, h2=slow（ 相对于h1已经走了 x )，那么 h1 走完 a 到达入环口的时候，h2 已经绕完环 n 圈也到达了入环口，所以 h1 和 h2 相遇的位置便是入环口的位置。

/*142. 环形链表 II
*/#include<iostream>
using namespace std;/* 链表类型 */
typedef struct ListNode {int val;ListNode* next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode* next) : val(x), next(next) {}};ListNode* detectCycle(ListNode* head) {if (head == nullptr || head->next == nullptr) return nullptr;if (head->next == head) return head;                            // 只有头结点ListNode* fast = head;ListNode* slow = head;while (fast != nullptr && fast->next != nullptr) {slow = slow->next;fast = fast->next->next;if (slow == fast) break;}if (fast == nullptr || fast->next == nullptr) return nullptr;   // 无环ListNode* h1 = head;ListNode* h2 = slow;while (h1 != h2) {h1 = h1->next;h2 = h2->next;}return h1;                                                      // 入环口
}

over!