Linked List Cycle - Leetcode Solution

The Linked List Cycle problem on LeetCode is a classic problem that involves identifying whether a linked list has a cycle or not. In this problem, you are given a linked list and are to determine whether it has a cycle or not.

A linked list consists of a series of nodes that are connected to each other. Each node contains a value and a reference to the next node in the list. If the last node in the list has a reference to null, then the linked list is considered to be terminated. However, if any node in the list references an earlier node, then the linked list contains a cycle.

To solve this problem, we need to use the Floyd's cycle-finding algorithm, also known as the "turtle and hare" algorithm. This algorithm involves traversing the linked list with two pointers, one moving faster than the other. If the linked list contains a cycle, then the faster pointer will eventually catch up to the slower pointer, indicating that a cycle has been found.

Here's the detailed solution:

1. We start by initializing two pointers, slow and fast, to point to the head of the linked list.
2. We then iterate through the linked list. During each iteration, the slow pointer moves one step forward while the fast pointer moves two steps forward.
3. We check at each step whether the fast pointer has reached the end of the list or not. If it has, then the linked list does not contain a cycle. Otherwise, we continue iterating through the list.
4. If the fast pointer catches up to the slow pointer, then a cycle has been found, and we return true. Otherwise, we return false.

Here's the Python code that implements this approach:

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head:
            return False
        
        slow = head
        fast = head.next
        
        while slow != fast:
            if not fast or not fast.next:
                return False
            
            slow = slow.next
            fast = fast.next.next
        
        return True

In the code above, we first check whether the head of the linked list is None. If it is, then we know for sure that the linked list does not contain a cycle (since there are no nodes to iterate through).

We then initialize the slow and fast pointers to point to the head of the linked list and its next node, respectively. We then iterate through the linked list using a while loop. During each iteration, we check whether the fast pointer has reached the end of the list (i.e., it is pointing to None), in which case we know for sure that the list does not contain a cycle. Otherwise, we move the slow pointer one step forward and the fast pointer two steps forward.

Finally, if the fast pointer ever catches up to the slow pointer, then we know that a cycle has been found, and we return True. Otherwise, we return False.

This solution has a time complexity of O(n), where n is the number of nodes in the linked list. It also has a space complexity of O(1), since we are only using two pointers to traverse the linked list.

1