题目描述
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：false 解释：链表中没有环。
思路及实现
方式一：快慢指针
思路
快慢指针是解决链表环问题的一个常见技巧。在这个方法中，我们设置两个指针，一个快指针（每次移动两步）和一个慢指针（每次移动一步）。如果链表中存在环，那么快指针最终会追上慢指针，即两者会在某个节点相遇；如果链表中没有环，那么快指针会先到达链表尾部（null）。
代码实现
Java版本
public class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } } public class Solution { public boolean hasCycle(ListNode head) { if (head == null || head.next == null) { return false; } ListNode slow = head; ListNode fast = head.next; while (slow != fast) { if (fast == null || fast.next == null) { return false; } slow = slow.next; fast = fast.next.next; } return true; } }
说明：
- 首先检查链表是否为空或只有一个节点，如果是，则肯定没有环。
- 初始化慢指针
slow指向头节点，快指针fast指向头节点的下一个节点。- 进入循环，如果快指针或快指针的下一个节点为空，则链表中没有环。
- 否则，慢指针每次移动一步，快指针每次移动两步，直到两者相遇或快指针到达链表尾部。
C语言版本
struct ListNode { int val; struct ListNode *next; }; bool hasCycle(struct ListNode *head) { if (head == NULL || head->next == NULL) { return false; } struct ListNode *slow = head; struct ListNode *fast = head->next; while (slow != fast) { if (fast == NULL || fast->next == NULL) { return false; } slow = slow->next; fast = fast->next->next; } return true; }
说明：
- C语言版本的实现与Java版本类似，只是语法和类型定义有所不同。
Python3版本
class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def hasCycle(self, head: ListNode) -> bool: if not head or not head.next: return False slow = head fast = head.next while slow != fast: if not fast or not fast.next: return False slow = slow.next fast = fast.next.next return True
说明：
- Python版本的实现也遵循同样的逻辑，使用类来定义链表节点，并在
Solution类中实现hasCycle方法。
复杂度分析
- 时间复杂度：O(n)，其中n是链表的长度。在链表有环的情况下，快指针每次移动两步，因此最坏情况下需要遍历链表长度的一半；
在链表没有环的情况下，快指针会先到达链表尾部，此时快指针最多遍历整个链表一次。因此，总的时间复杂度是O(n)。
- 空间复杂度：O(1)。我们使用了常数级别的额外空间来存储两个指针。
方式二：哈希表
思路
使用哈希表（在Python中通常使用字典）来存储已经访问过的节点。遍历链表时，对于每个节点，检查它是否已经在哈希表中。如果节点已经存在，说明链表中存在环；如果节点不存在，则将其添加到哈希表中。
代码实现
Java版本
import java.util.HashSet; import java.util.Set; public class Solution { public boolean hasCycle(ListNode head) { Set<ListNode> visited = new HashSet<>(); while (head != null) { if (visited.contains(head)) { return true; } visited.add(head); head = head.next; } return false; } }
说明：
- 使用
HashSet来存储访问过的节点。- 遍历链表，对于每个节点，检查它是否已经在
HashSet中。- 如果在
HashSet中找到了节点，则返回true表示存在环。- 如果遍历完整个链表都没有找到重复的节点，则返回
false表示没有环。
C语言版本
在C语言中，实现哈希表会稍微复杂一些，通常可以使用数组加哈希函数来模拟哈希表的行为。但考虑到C语言标准库中没有直接支持哈希表的数据结构，这里不展示C语言的哈希表实现，而是使用其他方法（如快慢指针）来解决。
Python3版本
class Solution: def hasCycle(self, head: ListNode) -> bool: visited = set() while head: if head in visited: return True visited.add(head) head = head.next return False
说明：
- Python中的字典（
dict）可以用来作为哈希表。- 遍历链表，使用字典
visited来存储访问过的节点。- 如果节点已经在
visited字典中，说明链表中存在环，返回True。- 如果遍历完整个链表都没有重复的节点，返回
False。
复杂度分析
- 时间复杂度：O(n)，其中n是链表的长度。我们最多需要遍历链表一次来检查每个节点。
- 空间复杂度：O(n)。在最坏的情况下，当链表中存在环时，我们可能需要将链表中的所有节点都添加到哈希表中。因此，空间复杂度与链表的长度成正比。
总结
| 方式 | 优点 | 缺点 | 时间复杂度 | 空间复杂度 |
| 快慢指针 | 简洁高效，不需要额外空间（除了指针） | 不适用于需要找到环的起始节点或环的长度的情况 | O(n) | O(1) |
| 哈希表 | 容易理解和实现，能够检测环的存在 | 需要额外的空间来存储访问过的节点 | O(n) | O(n) |
相似题目
| 相似题目 | 难度 | 链接 |
| 环形链表 II | 中等 | LeetCode 142 |
| 相交链表 | 中等 | LeetCode 160 |
| 链表中倒数第k个节点 | 中等 | LeetCode 19 |
| 删除链表的倒数第N个节点 | 中等 | LeetCode 143 |
| 重新排序链表 | 中等 | LeetCode 143 |
