链表

链表是一种常见的数据结构，用于存储线性序列。与数组不同，链表中的元素在内存中不是连续存储的，而是经过指针相连。链表由一个头指针指向链表的第一个节点，每个节点包含两个部分：数据域和指针域。数据域存储节点的数据，指针域指向下一个节点的地址。

链表有多种类型：

• 单向链表中每个节点只要一个指针域，指向下一个节点；
• 双向链表中每个节点有两个指针域，一个指向前一个节点，一个指向后一个节点；
• 环形链表中最终一个节点的指针域指向头节点，形成一个环。

环形链表

环形链表问题是一类十分经典的链表问题，给定一个单向链表，判别这个链表是否存在环或者环的状况。

这类问题一般有两种解法。

• 快慢指针法：运用两个指针，一个快指针和一个慢指针，快指针每次移动两个节点，慢指针每次移动一个节点，假如链表中存在环，则快指针最终会追上慢指针，否则快指针会抵达链表结尾完毕。这个算法的时刻复杂度是 O(n)，其间 n 是链表的长度。

• 哈希表法：遍历链表中的每个节点，每拜访一个节点就将它存储到哈希表中，假如拜访到了哈希表中已经存在的节点，说明链表中存在环。这个算法的时刻复杂度也是 O(n)，其间 n 是链表的长度，但需要额定的空间来存储哈希表。

快慢指针法其实便是 Floyd 判圈算法，接下来我们详细介绍一下：

Floyd判圈算法

Floyd判圈算法（又称龟兔赛跑算法）是一种快速检测链表中是否存在环的算法。该算法运用两个指针，一个慢指针和一个快指针，从链表头部开端同时向后遍历链表，每次快指针比慢指针多走一步，直到快指针走到链表结尾或者两个指针相遇。

假如链表中不存在环，那么快指针最终会走到链表的结尾，算法完毕。假如链表中存在环，那么快指针最终会在环内与慢指针相遇，算法会返回存在环的定论。

该算法的时刻复杂度为 $O(n)$，其间 $n$ 是链表的长度。因为该算法运用的是常数级别的额定空间，因而它是一种空间复杂度比较优异的算法。

Floyd 判圈算法的正确性能够经过数学归纳法来证明。

假设链表中存在环，且环的长度为 $k$。设慢指针走了 $x$ 步后进入环，快指针走了 $2x$ 步后进入环。设快指针比慢指针多走了 $y$ 圈（$y\ge 1$），则有：

其间 $z$ 表明慢指针在环内走的步数。因为快指针的速度是慢指针的两倍，所以能够得到：

也便是说，慢指针在环内走了 $k-x\%k$ 步。因为 $0\le x\%k<k$，因而 $0\le k-x\%k<k$，所以 $z>0$ 且 $z<k$。

因为快指针每次走两步，所以 $z$ 的取值只要 $k$ 种可能。当 $z=0$ 时，表明快指针与慢指针相遇，此刻算法会返回存在环的定论；当 $z\ne 0$ 时，表明快指针和慢指针在环内继续前进，因为快指针比慢指针多走了一圈，因而能够将 $x$ 的值更新为 $k-z$，这样快指针和慢指针都在环内间隔环进口的间隔为 $k-z$，再次相遇的位置便是环的进口。

由此可见，Floyd 判圈算法的正确性是得到了保证的。