LeetCode Tutorial in Python 141. Linked List Cycle #python #coding #leetcode

LeetCode Tutorial in Python 141. Linked List Cycle #python #leetcode

Solution 1 - Floyd's Tortoise and Hare Algorithm:

The intuition behind this solution lies in its similarity to a classic racing scenario between a tortoise and a hare. In this case, the tortoise is our 'slow' pointer, and the hare is our 'fast' pointer. Here's how it works:

Initialization: Initially, both pointers start at the head of the linked list.

The Race: The 'slow' pointer moves one step at a time, while the 'fast' pointer moves two steps at a time. This creates a scenario where the 'fast' pointer is covering ground twice as quickly as the 'slow' pointer.

Detecting a Cycle: If there is a cycle in the linked list, the 'fast' pointer will eventually catch up to the 'slow' pointer. This happens because the 'fast' pointer moves faster and may go around the cycle multiple times until it meets the 'slow' pointer.

Returning True: When the 'slow' and 'fast' pointers meet, it's a clear indication that there is a cycle in the linked list, and we return True.

No Cycle Detected: If the loop completes without the 'fast' pointer ever meeting the 'slow' pointer, it means there is no cycle in the linked list, and we return False.

The key insight here is that if there's a cycle, the 'fast' pointer will eventually catch up with the 'slow' pointer. This is a brilliant example of the Floyd's Tortoise and Hare algorithm, which is efficient and guarantees detection of a cycle in a linked list.

Time Complexity: The time complexity of this solution is O(N), where N is the number of nodes in the linked list. This is because in the worst case, both the 'slow' and 'fast' pointers traverse the entire list once. The loop terminates either when they meet (cycle detected) or when the 'fast' pointer reaches the end of the list (no cycle).

Space Complexity: The space complexity of this solution is O(1), which is constant. It's considered in-place because it only uses two extra pointers ('slow' and 'fast') to traverse the list, regardless of the size of the linked list. No additional data structures are used, making it very memory-efficient.

Solution 2 - Hashing Approach:

The intuition behind this solution is straightforward and relies on marking visited nodes within the linked list. Here's how it works:

Initialization: We start at the head of the linked list.

Marking Visited Nodes: As we traverse the linked list, we mark each visited node by setting its 'val' attribute to a specific value (in this case, 10^6).

Detecting a Cycle: If we encounter a node with its 'val' already set to 10^6 during traversal, it indicates that we've visited this node before, which means there is a cycle in the linked list.

Returning True: In this case, we return True to indicate the presence of a cycle.

No Cycle Detected: If the traversal completes without finding a node with 'val' equal to 10^6, it implies that there is no cycle in the linked list, and we return False.

The core idea here is that by marking visited nodes, we can detect cycles because we'll revisit a marked node if and only if there's a cycle.

Time Complexity: Similar to Solution 1, the time complexity of this solution is O(N), where N is the number of nodes in the linked list. The traversal of the entire list is required to mark visited nodes and detect a cycle.

Space Complexity: The space complexity of this solution is O(1) as well. Although we modify the 'val' attribute of each node, we are not using any additional data structures that depend on the size of the linked list. The space used is constant and does not grow with the input size.