LeetCode Solution 141 - Linked List Cycle

Problem Statement

Given the head of a linked list, determine if the linked list has a cycle in it.

A linked list cycle occurs when a node’s next pointer points back to a previous node instead of NULL, creating an infinite loop.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: The tail of the list connects to the second node (0-based index 1).

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: The tail of the list connects to the head.

Example 3:

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

Optimal Approach: Floyd’s Cycle Detection Algorithm (Tortoise and Hare)

Approach:

• Use two pointers: slow and fast.
• Move slow one step at a time and fast two steps at a time.
• If there is a cycle, slow and fast will eventually meet.
• If fast reaches NULL, there is no cycle.

C++ Solution (LeetCode-Compatible)

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

Step-by-Step Explanation of Code

1. Initialize two pointers: slow and fast, both pointing to head.
2. Loop until fast reaches the end:
   • Move slow one step.
   • Move fast two steps.
   • If slow == fast, a cycle is detected.
3. Return false if no cycle is found.

Dry Run / Execution Steps

Input: [3,2,0,-4] with cycle at pos = 1

Step	slow (moves 1 step)	fast (moves 2 steps)	Cycle detected?
1	3 -> 2	3 -> 0	No
2	2 -> 0	0 -> 2	No
3	0 -> -4	2 -> -4	No
4	-4 -> 2	-4 -> 2	Yes

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Reason for Not Choosing
Brute Force (HashSet)	O(N)	O(N)	Extra space required to store visited nodes
Two Pointers (Floyd’s Cycle Detection)	O(N)	O(1)	Most efficient, uses constant space

Complexity Analysis

• Time Complexity: O(N), since each node is visited at most once.
• Space Complexity: O(1), as no extra data structures are used.

Conclusion

The best approach to detect a cycle in a linked list is Floyd’s Cycle Detection Algorithm, which efficiently finds cycles in O(N) time and O(1) space.

Similar Problems for Practice:

1. Linked List Cycle II (Find the start of the cycle)
2. Remove Nth Node From End of List
3. Intersection of Two Linked Lists