指向任意节点的带环链表

🌈图示指向任意节点的带环链表

如图：

🌈快慢指针法判断链表是否带环

🌟思路：快指针fast一次走2步，慢指针slow一次走1步，fast先进环在换中运动，随后slow进入环。两指针每同时移动一次，二者的相对距离减少1，此时二者一定会在环中相遇。
🌟同时还可得出结论：相遇时slow不可能走过一整个环。相同时间内fast走过的路程是slow的二倍，fast和slow相遇时，slow一定不可能走过了一整个环（假设slow走过了一次整个环，则fast走过了两次环，在这期间二者一定会相遇，因此假设不成立）。
🌟图示fast和slow相遇过程：

🌟拓展思考：快指针fast一次走3步，慢指针slow一次走1步，此时一定会相遇吗？（C是圆环长度）
🌟答：不一定，当C-1为奇数时永远不会相遇。slow进环后，每同时移动一次，二者距离缩小2。当fast在slow后面且相隔1个节点时，再移动一次变成了fast在slow前且相隔1节点，进入了新一轮追逐，追逐距离还是是C-1（注意：追逐距离不是C-2），而C-1是奇数时，不管怎么减2，都不可能减为0，只会从1减到-1，又进入新一轮循环，追逐距离还是C-1，奇数，陷入死循环。

🌟根据原理类推，fast一次走4步，slow一次走一步，每次距离缩小3。当环的周长C为3的倍数时，会相遇，C的长度模3余2时，陷入死循环，循环时每轮追击距离为C-1；当环的周长模3余1时，陷入死循环，循环时每轮追击距离为C-2。

🌈找到带环链表中环的起始点

🌟由上文得出结论：fast和slow相遇时slow不可能走过一整个环，但是fast在slow进环前可能已经在环里走了好多圈了。此时fast大概率走了n-1圈但还没有走够n圈（当然巧合情况是fast刚好走了n圈），但是在fast追slow的过程中一定会把n圈补齐。
（想象一个L非常大，C非常小的带环链表），如下图：

🌟公式推导：
假设起点到入口点长度：L
假设环的周长：C
假设入口点到相遇点的数据：X
fast与slow相遇时:
slow走过的总长度：L+X；fast走过的总长度：L+n$\ast$c+X
列出方程：
2(L+X)=L+n$\ast$C+X ⇒ L+X=n$\ast$C ⇒ L=n$\ast$C-X
具象说明：一个指针从起点走，另一个指针从相遇点走，它们会在入口点相遇

☀️OJ题1：判断链表是否带环

链接: https://leetcode.cn/problems/linked-list-cycle/description/

思路：fast一次走两步，slow一次走一步，若有环则两指针一定会相遇。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head) {struct ListNode*fast=head,*slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(slow==fast)return slow;}return NULL;
}

☀️OJ题2：返回入环节点

链接: https://leetcode.cn/problems/linked-list-cycle-ii/description/

🌟法一：公式法（ L=n$\ast$C-X）。

先让fast和slow相遇，再让一个指针从相遇点走，另一个指针从头节点走，两指针相遇点即为入环节点。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* slow=head,*fast=head,*meet;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow){meet=fast;while(meet!=head){meet=meet->next;head=head->next;}return head;}}return NULL;
}

🌟法二：切断环，交叉链表求交点。

先让fast和slow相遇，从相遇点出断开环，此时演变为交叉链表求交点问题（先让长链表走差距步，再同时走，相遇处即环的起点）

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode*fast=head,*slow=head,*meet,*meetnext;struct ListNode*head1,*head2;int count1=0,count2=0;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow){meet=slow;meetnext=meet->next;meet->next=NULL;head1=head;head2=meetnext;while(head1){head1=head1->next;count1++;}while(head2){head2=head2->next;count2++;}int sub=count1-count2;head1=head;head2=meetnext;if(sub>0){while(sub--){head1=head1->next;}}else if(sub==0){;}else{while(sub++){head2=head2->next;}}while(head1!=head2){head1=head1->next;head2=head2->next;}return head1;}}return NULL;
}