思路一：哈希表

遍历链表，同时借助哈希表判断当前遍历到的节点是否已经被访问过，如果当前节点已被访问过，则说明存在环

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool hasCycle(ListNode *head) {// 空链表或只有一个节点，必定没有环if (head == nullptr || head->next == nullptr) {return false;}// 使用哈希表存储已访问的节点地址unordered_map<ListNode*, bool> visited;// 遍历链表ListNode* temp = head;while (temp != nullptr) {// 如果当前节点已被访问过，则说明存在环if (visited.find(temp) != visited.end()) {return true;}// 标记当前节点为已访问visited[temp] = true;temp = temp->next;}// 遍历结束，没有发现环return false;}
};

• 时间复杂度：O(N)
• 空间复杂度：O(N)

思路二：快慢指针

使用两个指针分别同时遍历链表，一个指针每次移动两个距离（称为快指针），另一个指针每次移动一个距离（称为慢指针），当快指针反过来追上慢指针时说明链表中出现了环

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool hasCycle(ListNode *head) {// 空链表或只有一个节点，必定没有环if (head == nullptr || head->next == nullptr) {return false;}//快慢指针初始化ListNode* slow = head;ListNode* fast = head->next;while(slow != fast){//快指针遍历了整个链表也没有追上慢指针，说明链表中不存在环if(fast == nullptr || fast->next == nullptr){return false;}//快慢指针进行移动slow = slow->next;fast = fast->next->next;}return true;}
};

• 时间复杂度：O(N)
• 空间复杂度：O(1)