141_linked_list_cycle.cpp

/*
LeetCode 141 - Linked List Cycle
Difficulty: Easy

Problem:
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached
again by continuously following the next pointer.
Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:
    Input: head = [3,2,0,-4], pos = 1
    Output: true

Example 2:
    Input: head = [1,2], pos = 0
    Output: true

Example 3:
    Input: head = [1], pos = -1
    Output: false

Constraints:
    The number of the nodes in the list is in the range [0, 10^4].
    -10^5 <= Node.val <= 10^5

Time Complexity: O(n)
Space Complexity: O(1)  - Floyd's Tortoise and Hare
*/

#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
};

int main() {
    Solution solution;

    // Create list with cycle: 3 -> 2 -> 0 -> -4 -> (back to 2)
    ListNode* n1 = new ListNode(3);
    ListNode* n2 = new ListNode(2);
    ListNode* n3 = new ListNode(0);
    ListNode* n4 = new ListNode(-4);
    n1->next = n2;
    n2->next = n3;
    n3->next = n4;
    n4->next = n2; // cycle
    cout << (solution.hasCycle(n1) ? "true" : "false") << endl; // true

    // No cycle
    ListNode* a = new ListNode(1);
    ListNode* b = new ListNode(2);
    a->next = b;
    cout << (solution.hasCycle(a) ? "true" : "false") << endl; // false

    return 0;
}