LeetCode第 141 题：环形链表(C++)

141. 环形链表 - 力扣（LeetCode）

快慢指针

慢指针：一次走一步 快指针：一次走两步 如果指向 NULL 则无环，若有环两者必然会相等。 注意边界条件判断。。

class Solution { public: bool hasCycle(ListNode *head) { // 1个结点无法构成环 if(head == NULL || head->next == NULL) return false; auto slow_p = head; auto fast_p = head->next; while(slow_p != fast_p){ if(fast_p == NULL || fast_p->next == NULL){ return false; }else{ slow_p = slow_p->next; fast_p = fast_p->next->next; } } return true; } };

标记法

把遍历过的节点值都置为一个不太可能出现的值。。。

class Solution { public: bool hasCycle(ListNode *head) { if(!head || !head->next) return false; while(head){ if(head->val == 137) return true; head->val = 137; head = head->next; } return false; } };

遍历链表，若有环，则必定有元素被重复遍历

利用关联容器unordered_set：

class Solution { public: bool hasCycle(ListNode *head) { unordered_set<ListNode *> c_set; while(head != NULL){ if(c_set.count(head)) return true; c_set.insert(head); head = head->next; } return false; } };