【C语言】【数据结构】【环形链表判断是否带环并返回进环节点】有数学推导加图解

数据结构】【环形链表判断是否带环并返回进环节点】有数学推导加图解"/>

【C语言】【数据结构】【环形链表判断是否带环并返回进环节点】有数学推导加图解

1.判断是否带环：

用快慢指针
slow指针一次走一步，fast指针一次走两步
当两个指针相遇时，链表带环；两个指针不能相遇时，当fast走到倒数第一个节点或为空时，跳出循环返回空指针。

那么slow指针一次走一步，fast指针一次走两步是否一定能追上呢？

fast永远比slow快一步，所以两者之间每走一次举例减少 1 即 N-1,N-2,N-3…0

那么fast一次走三步，slow一次走一步呢？

2.找第一个入环节点：

假设环的节点数为C，环之外的节点数是L
这里可以分为三种情况：
N是偶数——>slow走第一圈追上
N是奇数，C-1是偶数——>一定能追上
N是奇数，C-1是奇数呢？

推导： 3L=L+n*C-N
2L=n * C-N
若 C为偶数，N为奇数，那么 n * C-N 不会是偶数
所以 N是奇数，C-1是奇数的情况不存在
结论：
slow走1步，fast走3步时一定能追上

3.代码实现：

struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* slow=head;struct ListNode* fast=head;struct ListNode* meet=NULL;while(fast!=NULL&&fast->next!=NULL){slow=slow->next;fast=fast->next->next;if(slow==fast){meet=slow;goto next;}}return NULL;next:struct ListNode* cur=head;while(cur!=meet){cur=cur->next;meet=meet->next;}return meet;
}