algoadvance

Leetcode 141. Linked List Cycle

Problem Statement

The problem is to determine if a linked list has a cycle in it.

Specifically, we need to implement a function:

bool hasCycle(ListNode *head);

where ListNode is defined as:

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

The function should return true if there is a cycle in the linked list, and false otherwise.

Clarifying Questions

1. Input Constraints: Should we expect very large linked lists, or could there be edge cases like an empty list or a list with a single node?
2. Node Values: Do the values stored in the nodes have any significance for detecting the cycle? Or is it purely about the structure (i.e., the next pointers)?
3. Modification: Are we allowed to modify the list nodes (for instance, marking nodes)?

Strategy

The most efficient way to detect a cycle in a linked list is by using Floyd’s Cycle-Finding Algorithm (also known as the “tortoise and hare” algorithm), which uses two pointers:

1. Slow Pointer: Moves one step at a time.
2. Fast Pointer: Moves two steps at a time.

The idea is that if there isn’t a cycle, the fast pointer will eventually reach the end of the list. If there is a cycle, the fast pointer will eventually meet the slow pointer within the cycle.

Code

Here’s how you can implement the hasCycle function using Floyd’s Cycle-Finding Algorithm:

#include <iostream>

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

bool hasCycle(ListNode *head) {
    if (!head || !head->next) return false;

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

    while (fast != NULL && fast->next != NULL) {
        if (slow == fast) {
            return true;
        }
        slow = slow->next;
        fast = fast->next->next;
    }

    return false;
}

Time Complexity

• Time Complexity: O(n), where n is the number of nodes in the linked list. In the worst case, every node is visited once by each of the two pointers.
• Space Complexity: O(1), as we are not using any extra space that scales with input size, just a constant amount of space for the pointers.

Conclusion

This solution efficiently detects a cycle using Floyd’s Cycle-Finding Algorithm, which is optimal for this type of problem. It ensures that both time and space complexities are adequately managed, making it suitable for large linked lists.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?