141. 环形链表
题目描述
输入单链表的头节点 head，判断链表里有没有环。如果从某个节点出发不断沿 next 走，还能回到它自己，就说链表有环。
测试数据用数组给出节点值，并用整数 pos 说明尾节点的 next 连到哪个下标（从 0 开始）；pos = -1 表示没有环。pos 只用于构造链表，不会传给函数。
有环返回 true，否则返回 false。
示例 1
输入：head = [3,2,0,-4], pos = 1 输出：true
解释：尾节点 -4 连回下标 1 的节点 2，形成环。
示例 2
输入：head = [1,2], pos = 0 输出：true
解释：尾节点连回头节点，形成环。
示例 3
输入：head = [1], pos = -1 输出：false
解释：链表末尾为空，没有环。
数据范围
- 节点数在
[0, 10^4]之间。 -10^5 <= Node.val <= 10^5pos为-1，或是链表中合法的下标。
进阶：能否只用 O(1) 的额外内存判断？
解题思路：快慢指针
快指针每次走两步，慢指针每次走一步。有环时快慢指针必在环内相遇；无环时快指针先到 None。
为什么正确
若链表有环，slow 与 fast 都在同一环内，距离按模环长变化，最终会相遇。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
必须比较节点身份 is，不能只比较值；环中可能有重复值。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def hasCycle(self, head):
slow=fast=head
while fast and fast.next:
slow=slow.next; fast=fast.next.next
if slow is fast: return True
return Falseclass Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
}class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next; fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
};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
}var hasCycle = function(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next; fast = fast.next.next;
if (slow === fast) return true;
}
return false;
};function hasCycle(head: ListNode | null): boolean {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow!.next; fast = fast.next.next;
if (slow === fast) return true;
}
return false;
};其他解法
哈希法直观但要 O(n) 空间；快慢指针只用 O(1) 空间。
解法 2：哈希集合 时间 O(n)，空间 O(n)
顺着 next 遍历链表，把访问过的节点放入哈希集合。若遇到已经在集合中的节点，说明有环。若走到空指针，说明无环。
思路最直接。需要 O(n) 额外空间，不满足进阶要求。
class Solution:
def hasCycle(self, head):
seen = set()
while head:
if head in seen:
return True
seen.add(head)
head = head.next
return Falseclass Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> seen = new HashSet<>();
while (head != null) {
if (!seen.add(head)) return true;
head = head.next;
}
return false;
}
}class Solution {
public:
bool hasCycle(ListNode *head) {
unordered_set<ListNode*> seen;
while (head) {
if (!seen.insert(head).second) return true;
head = head->next;
}
return false;
}
};func hasCycle(head *ListNode) bool {
seen := map[*ListNode]bool{}
for head != nil {
if seen[head] {
return true
}
seen[head] = true
head = head.Next
}
return false
}var hasCycle = function(head) {
const seen = new Set();
while (head) {
if (seen.has(head)) return true;
seen.add(head);
head = head.next;
}
return false;
};function hasCycle(head: ListNode | null): boolean {
const seen = new Set<ListNode>();
while (head) {
if (seen.has(head)) return true;
seen.add(head);
head = head.next;
}
return false;
}