Linked List Cycle

Problem Statement

The objective is to determine the existence of a cycle within a given linked list. A cycle occurs if a node can be revisited by following the next pointers from any node. Notably, the position (pos) indicating the index where the tail node connects back to another node within the list is not provided as a parameter. The function should return true if a cycle exists in the linked list; otherwise, it should return false.

Examples

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 1st node (0-indexed).

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 0th node.

Example 3

Input:

head = [1], pos = -1

Output:

false

Explanation:

There is no cycle in the linked list.

Constraints

• The number of the nodes in the list is in the range [0, 104].
• -105 <= Node.val <= 105
• pos is -1 or a valid index in the linked-list.

Approach and Intuition

To solve the cycle detection problem in linked lists, let's consider how we can approach it using intuition derived from the problem's constraints and examples:

• In Example 1, the list models a cycle: by following the next pointers from the head, we return to an earlier node. Essentially, you would walk through the list and find yourself visiting a previously visited node.
• In contrast, Example 3 illustrates a non-cyclical list with only one node not linked to itself or any other node.

Let's delve into an approach based on this intuition:

1. Use of Two-Pointer Technique (Floyd's Tortoise and Hare Algorithm):

   • Employ two pointers at different speeds — one moving one step at a time (slow) and the other moving two steps at a time (fast).
   • If the linked list has a cycle, these two pointers are expected to meet at some point (as the fast pointer will eventually lap the slow pointer).
   • If the fast pointer or its next pointer becomes null, then the list doesn't have a cycle.

2. Other Considerations:

   • Address edge cases such as lists with zero nodes (return false immediately), and single-node lists to prevent infinite loops or null references.
   • According to constraints, handle list lengths up to 10,000 and node values from -105 to 105, ensuring the algorithm remains efficient and effective within these bounds.

This approach allows us to detect cycles without needing additional memory for storage — a significant advantage in environments with limited memory resources.

Solutions

class Solution {
public:
    bool checkCycle(ListNode* start) {
        if (!start) {
            return false;
        }
        ListNode* slowPtr = start;
        ListNode* fastPtr = start->next;
        while (slowPtr != fastPtr) {
            if (!fastPtr || !fastPtr->next) {
                return false;
            }
            slowPtr = slowPtr->next;
            fastPtr = fastPtr->next->next;
        }
        return true;
    }
};