链表一：寻找环形链表的入口点

寻找环形链表的入口点

• 环形链表的入口点
• • 1.首先怎么判断链表是否有环
  • • （1）为什么slow走一步，fast走两步，他们一定会在环里面相遇，会不会永远追不上?请证明！
    • （2）slow走一步，fast走3步？走4步？走x步行不行？为什么？请证明！
  • 2.找入环点

环形链表的入口点

1.首先怎么判断链表是否有环

寻找环形链表入口点的第一步，要先判断该链表是否为环形链表，环形链表的尾指针指向的位置是不确定的，它可以在任何位置成环。
如下面这些图所示：

那么如何判断是否有环呢？我们可以采用双指针法，思路如下：
具体地，我们定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。初始时，快、慢指针在位置 head。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。
代码如下：

bool hasCycle(struct ListNode *head) 
{struct ListNode *slow=head;     //慢指针struct ListNode *fast=head;     //快指针//慢指针一次走一步，快指针一次走两步while(fast!=NULL&&fast->next!=NULL){slow=slow->next;fast=fast->next->next;if(slow==fast){return true;}}return false;
}

对于以上代码我们难免会提出以下两个问题；

（1）为什么slow走一步，fast走两步，他们一定会在环里面相遇，会不会永远追不上?请证明！

答：
不会追不上。假设slow进环的时候，fast与slow的距离是N，紧接着追击的过程中（fast追slow）fast向前走两步，slow走一步，他们每次一走，它们之间的距离就会缩小1，由一开始相距N，到后面相距0。
![在这里插入图片描述](.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NzgxMjYwMw==,size_16,color_FFFFFF,t_70

从表中我们会发现它们之间的距离就会缩小1由一开始相距N，到后面相距为0。
不管进环时，它们相距的距离是偶数还是奇数。最终我们发现一定fast一定会追上slow。
例如下面这个例子：
假设环里面只有8个节点，此时如slow与fast的位置如左下图所示：

最终fast与slow会在相遇点相遇

（2）slow走一步，fast走3步？走4步？走x步行不行？为什么？请证明！

此时我们就可以发现要发生相遇与fast走的步数和环中的节点数有关。
我们设fast走X步，环中结点数为Y

2.找入环点

经过上图我们分析我们可以写出如下代码：

struct ListNode *detectCycle(struct ListNode *head) 
{struct ListNode* slow = head;     //慢指针struct ListNode* fast = head;     //快指针//慢指针一次走一步，快指针一次走两步while (fast != NULL && fast->next != NULL){slow = slow->next;fast = fast->next->next;if (slow == fast){//相遇结点struct ListNode*meet=fast;while(meet!=head){meet=meet->next;head=head->next;}return meet;}}return NULL;
}

链表一：寻找环形链表的入口点

寻找环形链表的入口点

• 环形链表的入口点
• • 1.首先怎么判断链表是否有环
  • • （1）为什么slow走一步，fast走两步，他们一定会在环里面相遇，会不会永远追不上?请证明！
    • （2）slow走一步，fast走3步？走4步？走x步行不行？为什么？请证明！
  • 2.找入环点

环形链表的入口点

1.首先怎么判断链表是否有环

寻找环形链表入口点的第一步，要先判断该链表是否为环形链表，环形链表的尾指针指向的位置是不确定的，它可以在任何位置成环。
如下面这些图所示：

那么如何判断是否有环呢？我们可以采用双指针法，思路如下：
具体地，我们定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。初始时，快、慢指针在位置 head。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。
代码如下：

bool hasCycle(struct ListNode *head) 
{struct ListNode *slow=head;     //慢指针struct ListNode *fast=head;     //快指针//慢指针一次走一步，快指针一次走两步while(fast!=NULL&&fast->next!=NULL){slow=slow->next;fast=fast->next->next;if(slow==fast){return true;}}return false;
}

对于以上代码我们难免会提出以下两个问题；

（1）为什么slow走一步，fast走两步，他们一定会在环里面相遇，会不会永远追不上?请证明！

答：
不会追不上。假设slow进环的时候，fast与slow的距离是N，紧接着追击的过程中（fast追slow）fast向前走两步，slow走一步，他们每次一走，它们之间的距离就会缩小1，由一开始相距N，到后面相距0。
![在这里插入图片描述](.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NzgxMjYwMw==,size_16,color_FFFFFF,t_70

从表中我们会发现它们之间的距离就会缩小1由一开始相距N，到后面相距为0。
不管进环时，它们相距的距离是偶数还是奇数。最终我们发现一定fast一定会追上slow。
例如下面这个例子：
假设环里面只有8个节点，此时如slow与fast的位置如左下图所示：

最终fast与slow会在相遇点相遇

（2）slow走一步，fast走3步？走4步？走x步行不行？为什么？请证明！

此时我们就可以发现要发生相遇与fast走的步数和环中的节点数有关。
我们设fast走X步，环中结点数为Y

2.找入环点

经过上图我们分析我们可以写出如下代码：

struct ListNode *detectCycle(struct ListNode *head) 
{struct ListNode* slow = head;     //慢指针struct ListNode* fast = head;     //快指针//慢指针一次走一步，快指针一次走两步while (fast != NULL && fast->next != NULL){slow = slow->next;fast = fast->next->next;if (slow == fast){//相遇结点struct ListNode*meet=fast;while(meet!=head){meet=meet->next;head=head->next;}return meet;}}return NULL;
}