Linked List Cycle easy

Problem Statement

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. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

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 Explanation: There is a cycle in the linked list, where the tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the first node.

Example 3:

Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list.

Steps to Solve

1. Fast and Slow Pointers: We use two pointers, a "slow" pointer and a "fast" pointer. The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time.

2. Cycle Detection: If there's a cycle, the fast pointer will eventually lap the slow pointer. If they meet, a cycle exists.

3. No Cycle: If the fast pointer reaches the end of the list (i.e., fast becomes nullptr), there's no cycle.

Explanation

The algorithm leverages the fact that if a cycle exists, the fast pointer will inevitably catch up to the slow pointer. Imagine the slow pointer as a runner completing one lap of a track at a time, and the fast pointer as a runner completing two laps per cycle. Eventually, they will meet.

The absence of a nullptr check for the slow pointer is intentional. If the slow pointer reaches the end, it implies that the fast pointer must have reached the end as well (since the fast pointer always remains ahead or at the same node as the slow pointer), so there is no cycle.

Code

#include <iostream>

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

bool hasCycle(ListNode *head) {
    if (head == nullptr || head->next == nullptr) return false; //Handle empty or single-node lists

    ListNode *slow = head;
    ListNode *fast = head->next;

    while (slow != fast) {
        if (fast == nullptr || fast->next == nullptr) return false; // No cycle
        slow = slow->next;
        fast = fast->next->next;
    }
    return true; // Cycle detected
}


int main() {
    // Example usage:
    ListNode* head1 = new ListNode(3);
    head1->next = new ListNode(2);
    head1->next->next = new ListNode(0);
    head1->next->next->next = new ListNode(-4);
    head1->next->next->next->next = head1->next; // Create a cycle

    std::cout << "Example 1: " << (hasCycle(head1) ? "true" : "false") << std::endl;


    ListNode* head2 = new ListNode(1);
    head2->next = new ListNode(2);
    std::cout << "Example 2: " << (hasCycle(head2) ? "true" : "false") << std::endl;

    ListNode* head3 = new ListNode(1);
    std::cout << "Example 3: " << (hasCycle(head3) ? "true" : "false") << std::endl;

    // Clean up memory (important to avoid memory leaks)
    // ... (Implementation to delete linked list nodes would go here)


    return 0;
}

Complexity

• Time Complexity: O(n), where n is the number of nodes in the linked list. In the worst case, the slow pointer traverses the entire list.

• Space Complexity: O(1). The algorithm uses only a constant amount of extra space for the slow and fast pointers.