Problem
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
Solution1: HashTable
Time complexity: O(n)
Space complexity: O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua // Running time: 16 ms class Solution { public: bool hasCycle(ListNode *head) { unordered_set<ListNode*> seen; while (head) { if (seen.count(head)) return true; seen.insert(head); head = head->next; } return false; } }; |
Solution2: Fast + Slow pointers
Time complexity: O(n)
Space complexity: O(1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua // Running time: 8 ms class Solution { public: bool hasCycle(ListNode *head) { auto slow = head; auto fast = head; while (fast) { if (!fast->next) return false; fast = fast->next->next; slow = slow->next; if (fast == slow) return true; } return false; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment