【实战】ACM 选手图解 LeetCode 环形链表

大家好呀，我是蛋蛋。

今天来切环形链表题，依然是面试高频题。

判断环形链表在思维上稍微复杂一点儿，但是不慌，有我在。

LeetCode 141：环形链表

题意

给定一个链表，判断链表中是否有环。

示例

使用整数 pos 表示链表尾连接到链表中的位置(索引从 0 开始)。

输入：head = [3, 2, 0, -4]，pos = 1

输出：true

解释：链表中有一个环，其尾部连接到第 2 个节点。

输入：head = [1]，pos = -1

输出：false

解释：链表中没有环。

提示

• pos 不作为参数进行传递，仅标识链表的实际情况。

• 0 <= 链表节点数 <= 10^4

• 10^-5 <= Node.val <= 10^5

• pos 为 -1 或者链表中的一个有效索引。

题目解析

难度简单，解题方法古怪，在实际应用中应该没人脑子瓦特用这种方法。

这种古怪的解题方法就是：快慢指针。

快慢指针，顾名思义，是使用速度不同的指针（可用在链表、数组、序列等上面），来解决一些问题。

这些问题主要包括：

• 处理环上的问题，比如环形链表、环形数组等。
• 需要知道链表的长度或某个特别位置上的信息的时候。

快慢指针这种算法证明，它们肯定是会相遇的，快的指针一定会追上慢的指针，可以理解成操场上跑步，跑的快的人套圈跑的慢的人。

一般用 fast 定义快指针，用 slow 定义慢指针。
速度不同是指 fast 每次多走几步，slow 少走几步。一般设定的都是 fast 走 2 步，slow 走 1 步。

当然设置成别的整数也是可以的，比如 fast 走 3 步，slow 走 1 步。

图解