141. Linked List Cycle

發表於 | 分類於

problem

solution

two pointer ，slow fast pointers 用於linked list檢查是否包含環

option 1

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode *> s;
        ListNode *cur = head;
        while(cur){
            if(s.find(cur)!=s.end()) return true;
            s.insert(cur);
            cur = cur->next;
        }
        return false;
    }
};

option 2 - Two pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(!head ) return head;
        ListNode *slow =head, *fast = head;
        while(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
            if(slow==fast) return true;
        }
        return false;        
    }
};

analysis

  • option 1
    • time complexity O(n)
    • space complexity O(n)
  • option 2
    • time complexity O(n)
    • space complexity O(1)