【算法随想录01】环形链表

题目：141. 环形链表
难度：EASY

代码

哈希表遍历求解，表中存储的是元素地址。

• 时间复杂度 $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) {unordered_set<ListNode*> seen;while (head != nullptr) {if(seen.count(head))  // 如果之前存储过该地址，证明之前访问过，有环。return true;seen.insert(head);head = head->next;}return false;}
};

快慢双指针，药到病除

• 算法思想：当链表中存在环时，快指针会和慢指针相等。否则，慢指针永远不可能赶上快指针。
• 时间复杂度：$O(N)$，空间复杂度：$O(1)$

/*** 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 && slow != nullptr && fast != nullptr) {slow = slow->next;if (fast->next == nullptr)return false;fast = fast->next->next;}if (slow == fast) return true;else return false;}
};