Leetcode: 141. Linked List Cycle

Linked List Cycle - Solution Explanation

Code Implementation

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        bool hasCycle(ListNode *head) {
            if (head == NULL)
                return false; 
            ListNode* slow = head; 
            ListNode* fast = head->next;
            while (slow !=fast)
            {
                if (fast == NULL || fast->next == NULL)
                    return false; 
                slow = slow->next; 
                fast = fast->next->next;
            }
            return true;
        }
    };
  

Complexity Analysis

The given solution uses the Floyd's Cycle Detection Algorithm to determine whether a linked list has a cycle. Let's analyze the complexity:

• Time Complexity: O(n) - In the worst case, the slow and fast pointers will meet after traversing the entire linked list, which takes O(n) operations, where n is the number of nodes in the list.
• Space Complexity: O(1) - The algorithm uses a constant amount of extra space for the two pointers, regardless of the size of the input linked list.

Example

Let's consider an example to understand how the code works:

    Input: 1 -> 2 -> 3 -> 4 -> 2 (Node with value 2 points back to a previous node)
    Output: true
  

In this example, the linked list has a cycle. The code will use the Floyd's Cycle Detection Algorithm to determine the presence of a cycle. The slow and fast pointers will eventually meet, indicating the presence of a cycle, and the code will return true.

Conclusion

In this blog post, we discussed a solution to detect cycles in a linked list using the Floyd's Cycle Detection Algorithm. We provided the code implementation, explained its complexity, and provided an example to illustrate its usage. This solution can be used to efficiently determine whether a given linked list contains a cycle.