环形链表，这就是送分题了，不少大厂面Agent岗位，都会来一道简单算法题。
京东、小红书、快手，今年（26年）春招都有考察过：
141、 环形链表：https://leetcode.cn/problems/linked-list-cycle/
题目描述
给你一个链表的头节点 head，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则该链表中没有环。
注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true；否则，返回 false。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
提示：
链表中节点的数目范围是 [0, 10^4]-10^5 <= Node.val <= 10^5pos为-1或者链表中的一个有效索引
思路
最直观的做法，是用哈希表记录访问过的节点。如果再次访问到同一个节点，说明链表有环。
这种方法可以通过本题，但需要 O(n) 的额外空间。有没有只使用常量空间的办法呢？
那么就应该想到快慢指针了：
slow每次走一个节点；fast每次走两个节点；如果链表无环， fast会先走到链表末尾；如果链表有环， fast和slow最终一定会在环内相遇。
很多录友能记住这个结论，但为什么有环就一定会相遇，而不是一直错开呢？
首先，fast 走得更快，所以它一定比 slow 先进入环。等两个指针都进入环后，可以把这个过程想象成在环形跑道上追赶。
每轮移动，fast 走两步，slow 走一步。相对于 slow 来说，fast 每轮只向前靠近一个节点。
也就是说，两个指针在环上的距离每轮都会缩短一格，不会跳过彼此。因此只要链表有环，它们就一定会在某个节点重合。
注意循环条件必须写成 fast != nullptr && fast->next != nullptr。因为 fast 每次要走两步，访问 fast->next->next 之前，必须先保证 fast 和 fast->next 都不为空。
模拟过程
以 head = [3,2,0,-4]，pos = 1 为例，链表尾节点 -4 指向节点 2：
开始时， slow和fast都指向头节点3。第一轮移动后， slow指向2，fast指向0。第二轮移动后， slow指向0，fast绕过链表尾部后指向2。第三轮移动后， slow和fast都指向-4。两个指针指向同一个节点，因此链表中存在环，返回 true。
整个追赶过程如下：
如果链表没有环，fast 最终会指向空节点，或者 fast->next 为空，此时退出循环并返回 false。
解题代码
class Solution {
public:
bool hasCycle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
// fast 每次走两步，所以还要判断 fast->next 是否为空
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) { // 相遇说明链表中存在环
return true;
}
}
return false;
}
};
复杂度分析
时间复杂度： O(n)。无环时最多遍历链表一次；有环时，快慢指针会在有限轮移动后相遇。空间复杂度： O(1)。只使用了两个指针。
其他语言
Python3
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast: # 比较节点本身，而不是节点值
return True
return False
Java
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) { // 相遇说明链表中存在环
return true;
}
}
return false;
}
}
Go
func hasCycle(head *ListNode) bool {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast { // 相遇说明链表中存在环
return true
}
}
return false
}
JS
var hasCycle = function(head) {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) { // 相遇说明链表中存在环
return true;
}
}
return false;
};
与代码随想录联系
本题是快慢指针在链表中的经典应用。代码随想录的环形链表也讲解了为什么两个指针一定会相遇。
做完本题，建议继续做142. 环形链表 II。本题只判断有没有环，142 题还要通过数学推导找到环的入口，是对快慢指针更进一步的运用。