Home | Projects | Notes > Problem Solving > LC - E - 141. Linked List Cycle (unordered_set, Floyd's Cycle Detection Algorithm - Two Pointers)

LC - E - 141. Linked List Cycle (unordered_set, Floyd's Cycle Detection Algorithm - Two Pointers)

Solutions in C++

Solution 1

This solution uses STL unordered_set container.

Complexity Analysis:

$T = O(n)$ $n$ is the number of elements in the given linked list
$S = O(n)$ as additional memory space is used for unordered_set container

Solution:


xxxxxxxxxx
25
1
/**
2
 * Definition for singly-linked list.
3
 * struct ListNode {
4
 *     int val;
5
 *     ListNode *next;
6
 *     ListNode(int x) : val(x), next(NULL) {}
7
 * };
8
 */
9
class Solution {
10
public:
11
    bool hasCycle(ListNode *head) {
12
        set<ListNode*> s;
13

14
        while (head)
15
        {
16
            if (s.find(head) != s.end())
17
                return true;
18
            
19
            s.insert(head);
20
            head = head->next;
21
        }
22
        
23
        return false;        
24
    }
25
};

Solution 2

This solution uses the Floyd's Cycle Detection Algorithm; the Two Pointers approach. A fast pointer and a slow pointer are used to determine if there exists a cycle in the loop.

The slow pointer moves one node ahead at a time.
The fast pointer moves two nodes ahead at a time.

If a loop exists in the linked list, the fast and slow pointers are bound to meet at some point.

Complexity Analysis:

$T = O(n)$ $n$ is the length of the given string s
$S = O(1)$ as constant memory space is used

Solution:


xxxxxxxxxx
26
1
/**
2
 * Definition for singly-linked list.
3
 * struct ListNode {
4
 *     int val;
5
 *     ListNode *next;
6
 *     ListNode(int x) : val(x), next(NULL) {}
7
 * };
8
 */
9
class Solution {
10
public:
11
    bool hasCycle(ListNode *head) {
12
        ListNode *slow = head;
13
        ListNode *fast = head;
14

15
        while (fast && fast->next && fast->next->next)
16
        {
17
            slow = slow->next;
18
            fast = fast->next->next;
19

20
            if (slow == fast)
21
                return true;
22
        }
23

24
        return false;
25
    }
26
};