链表的实现（单链表、双链表、环形表）【下】超详细！！

环形链表1

在介绍环形表时，我们主要以题目的形式进行讲解呈现。

题目链接：https://leetcode.cn/problems/linked-list-cycle/

对于这个题，思路为快慢指针，让快指针走两步，慢指针走一步，如果两指针相遇，则说明该链表带环。具体实现如下：

#include<stdio.h>​ #include<stdbool.h> typedef int SLDataType; typedef struct ListNode { SLDataType x; struct ListNode* next; }ListNode; bool hasCycle(ListNode* head) { ListNode* fast = head; ListNode* slow = head; while (fast&&fast->next) { //慢指针走一步，快指针走两步 slow = slow->next; fast = fast->next->next; if (fast == slow)//快慢指针相遇 { return true; } } //两指针始终没有相遇，即不存在环 return false; }

但问题是：为什么快慢指针相遇就会带环？如何证明？以及如果快指针如果走3步、4步......呢？

证明推理如下：如果链表当中存在环，快指针一次走两步，慢指针一次走一步，那么在慢指针即将入环前，快指针已经入环，且两者此刻相距为N，且两者走一步，距离就-1，所以fast与slow距离变化为：N,N-1,N-2,N-3......1,0。所以如果存在环，快指针走两步，慢指针走一步，两者会相遇。

但，如果走3、4、5......呢？

如果慢指针走1步，快指针走3步，两者步差为2，当slow即将入环的一刻，假设fast与slow之间距离为N。

①当N为偶数时，快慢指针相距的距离为：N,N-2,N-4,N-6......2,0(相遇)。

②当N为奇数时，快慢指针相距的距离为：N,N-2,N-4,N-6......3,1,-1(错过)。

假设环的周长为C，当错过时，快指针追慢指针，两者相距的距离为C-1。

当C-1为偶数时，第二圈会相遇(①中已说明)。

当C-1为奇数时，不会相遇，会一直错过（②中已说明）

所以总结出来限制条件：N为奇数，C-1为奇数，即C为偶数，快慢指针不会相遇。

那么这个结论到底对不对呢？

假设环的周长为C，所以快指针走过的路程为fast：L+xC(走过的圈数)+C-N(快慢指针相距的距离)，slow：L。又因为快指针一次走三步，慢指针一次走一步，所以：3slow = fast；

代入得：3L = L+xC+C-N,所以：2L = xC+C-N=C(c+1)-N。2L肯定为偶数，所以xC+C-N为偶数，那么就有这两种可能：

①偶数-偶数 = 偶数；

②奇数-奇数 = 偶数；

排除①，因为限制结论为N为奇数，C为偶数。那么看②，则C(x+1)为奇数,又因为x为跑了多少圈，对过程分析影响不大，所以可以忽略，因此这里得出C为奇数，显然与之前得出得结论不符，所以N为奇数，C为偶数不存在，即不管怎么快慢指针始终相遇。同理快指针走4、5、6......证明同上。

环形链表2

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

对于环形表2，思路同样为快慢指针，不过还需要一个指向头节点的指针，当快慢指针相遇时，让指向头节点的指针与相遇点指针步频为都走一步，指向头节点指针与快慢指针相遇点指针再次相遇的地方为入环节点。

#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h>​ typedef int SLDataType; typedef struct ListNode { SLDataType x; struct ListNode* next; }ListNode; ListNode* FindMidNode(ListNode* head) { ListNode* fast = head; ListNode* slow = head; while (fast && fast->next) { //慢指针走一步，快指针走两步 slow = slow->next; fast = fast->next->next; if (fast == slow)//快慢指针相遇 { return slow; } } } ListNode* DetectCycle(ListNode* head) { //找相遇点 ListNode* meet = FindMidNode(head); //相遇点与头节点相遇的位置即为入环位置 ListNode* pcur = head; while (meet && pcur) { if (pcur == meet)//可能头尾相连，并且相遇点在头节点，所以先判断 { return meet; } meet = meet->next; pcur = pcur->next; } //链表不带环 return NULL; }

证明过程如下：

假设相遇点M为Meet，E为入环节点，L为指向头节点you的指针到入环节点的距离，E到M距离为X，原周长为R，slow指针走的距离为：L+X,fast指针走的距离为：L+X+nR，又因为fast = 2*slow，所以：L+X+nR = 2*(L+X)，所以：L = nR-X，即：L = (n-1)R+(R-X)。又因为n最小取1(在slow入环前，fast就已经走到了M点，当后续又在M点相遇，fast最少走了一圈，所以n取值为1、2、3、4、5、6......),(n-1)R为圈数，对逻辑推理影响不大，取n = 1，所以L = R-X。所以指向头节点的指针与Meet指针各走一步，会在入环位置相遇。