今天，带来链表相关算法的讲解。文中不足错漏之处望请斧正！

理论基础点这里

---

环形链表

1. 思路

利用链表相交

我们在环内任意一处断开，然后判断断开处的下一个位置和head是否相交，如果相交，相交处就是环口。

公式法

1. 利用快慢指针判断是否有环
2. 计算环内和环外的相交节点，即环的入口

快慢指针怎么判断是否有环？

如果有环，快指针一定先进环，慢指针后进环。都在环内后，快指针会开始追赶慢指针，最后一定会追上。为什么一定会追上呢？我们让快指针每次走两步，慢指针每次走一步，快慢指针走一次，距离就缩减一步，最终一定会追上。

环内外的相交节点为什么是环的入口？

如图，定义head到环口的距离为x，环口到快慢指针相遇点的距离为y，快慢指针相遇点到环口的距离为z。

slow入圈后不会转圈，在 环口 或 第二次到环口前 就直接和fast相遇，所以slow移动距离为x + y。

fast可能在slow入圈前转了n圈，所以fast移动距离为x + y + n(y + z)。

又因为fast的速度是slow的2倍，所以fast的移动距离也是slow的2倍：

2(x + y) = x + y + n(y + z)

其中n≥1。

x + y = n(y + z)

x = n(y + z) - y

x = (n - 1)(y + z) + z

代值，当n=1：

x = z

不管转了多少圈，从起点到环口的距离始终等于相遇处到环口的距离。

因此，我们给一个inRing和一个outRing，分别表示环内相遇处和环外头节点的位置，让他俩同步走，最后相遇位置就是环口。

为什么slow入圈后不会转圈，会在环口直接fast相遇？

难道slow入圈后不能转上几圈吗？

情况1：slow刚入圈在环口时，fast也在环口

这种情况slowslow不会转圈，会在环口直接和fast相遇。

情况2：slow刚入圈在环口时，fast在环内某一位置

当fast走了k+n的距离，slow会走(k+n) / 2的距离。因为k比n小，所以(k+n) / 2小于n。

这种情况下，fast已经走到了环口，而slow还没走到. 而fast和slow的相对距离每次只减一, 这就说明, 在环口3前，fast已经一步一步追上了slow。slow不会转圈。

综上，slow会在环口或环口前和fast相遇。

2. 参考代码

class Solution {
public:// 题意: 找到环口// 建模1: 把环内一处断开, 把环外的head 和 环内的切口 看作两个链表头, 利用链表相交来获取相交位置ListNode *detectCycle(ListNode *head) {if (head == nullptr) return nullptr;// 1. 找到环内一处, 断开ListNode *slow = head;ListNode *fast = head;ListNode *cycleCut = nullptr;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;if (slow == fast) break;}if (slow != fast) return nullptr;else {cycleCut = slow->next;slow->next = nullptr;}// 2. 利用链表相交来获取相交位置return getIntersectionNode(head, cycleCut);}private:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {// 1. 计算长度差gapint sizeA = getSize(headA);int sizeB = getSize(headB);int gap = abs(sizeA - sizeB);// 2. 长的链表先走gap步 -- 二表长度相同ListNode *&longList = sizeA > sizeB ? headA : headB;while (gap--) longList = longList->next;// 3. 二表同时走, 走某步时两表指针指向同一个元素就表示链表在此处相交while (headA != nullptr) {if (headA == headB) return headA;headA = headA->next;headB = headB->next;}return nullptr;}int getSize(ListNode *head) {int size = 0;while (head != nullptr) {head = head->next;++size;}return size;}
};

class Solution {
public:    // 题意: 找到环口// 建模2: 公式法 -- 环内相遇处到环口的距离 = 环外head到环口的距离ListNode *detectCycle(ListNode *head) {ListNode *slow = head;ListNode *fast = head;ListNode *outRing = head;ListNode *inRing = nullptr;// 快慢指针相遇处 = 环内while (fast && fast->next) {slow = slow->next;fast = fast->next->next;if (slow == fast) {inRing = slow;while (inRing != outRing) {inRing = inRing->next;outRing = outRing->next;}return inRing; // 此时inRing和outRing已经在环口相遇                }}return nullptr;}
};

---

今天的分享就到这里了，感谢您能看到这里。

这里是培根的blog，期待与你共同进步！