题目:141. 环形链表
难度:EASY
代码
哈希表遍历求解,表中存储的是元素地址。
- 时间复杂度 O ( N ) O(N) O(N),空间复杂度 O ( N ) 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(N) O(N),空间复杂度: O ( 1 ) O(1) 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;}
};