Linked List Cycle Leetcode Problem 141 [Python Solution]

In this blog post, we will tackle the Linked List Cycle problem, which is a part of LeetCode's Blind 75 List.

This problem falls under the category of Linked List and is considered easy in terms of difficulty.

We will explore an efficient Python solution for this problem.

Problem Overview

The problem statement is as follows:

Given the head of a linked list, your task is to determine if the linked list has a cycle in it.

A cycle exists in a linked list if there is a node in the list that can be reached again by continuously following the next pointer.

It's important to note that the pos variable is used to denote the index of the node where the tail's next pointer is connected to, but it is not passed as a parameter.

You need to return true if there is a cycle in the linked list; otherwise, return false.

Example

Let's look at an example:

Input:

head = [3, 2, 0, -4], pos = 1


Output:

true


Explanation:
There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Understanding Constraints

Before we dive into the solution, it's crucial to understand the constraints provided in the problem:

• The number of nodes in the list falls within the range [0, 10^4].
• Node values are within the range of -10^5 to 10^5.
• The pos variable can be -1 or a valid index in the linked list.

Efficient Python Code Solution

We will now discuss an efficient Python solution to the Linked List Cycle problem using the "Tortoise and Hare" algorithm.

This algorithm allows us to determine whether a cycle exists in the linked list without using additional memory.

def hasCycle(self, head: ListNode) -> bool:
    slow, fast = head, head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

The code above defines a function hasCycle that takes the head of the linked list as input and returns True if a cycle exists, and False otherwise.

Let's break down the code and understand how it works.

1. The "Tortoise and Hare" Algorithm

The core of this solution is the "Tortoise and Hare" algorithm, which uses two pointers: a slow pointer (slow) and a fast pointer (fast).

These pointers start at the head of the linked list, and they move through the list at different speeds.

• The slow pointer moves one step at a time, while the fast pointer moves two steps at a time.
• If there is a cycle in the linked list, the fast pointer will eventually catch up to the slow pointer, leading to a meeting point.

2. Loop Detection

In the while loop, we continuously advance the slow and fast pointers.

The loop continues as long as both fast and fast.next are not None.

If there is no cycle, the fast pointer will reach the end of the linked list (fast.next will be None), and we exit the loop, returning False.

3. Meeting Point

If there is a cycle, the fast pointer will eventually catch up to the slow pointer, leading to a meeting point.

When slow and fast meet (slow == fast), we return True to indicate the presence of a cycle in the linked list.

This algorithm runs in linear time complexity, as it visits each node at most once.

It also has constant space complexity, as it uses only two pointers.

Time and Space Complexity

• Time Complexity: O(n), where n is the length of the linked list.
• Space Complexity: O(1), as we only use a constant amount of extra space for the two pointers.

Reasoning Behind Our Approach

The "Tortoise and Hare" algorithm is a clever technique for detecting cycles in a linked list.

By having two pointers move at different speeds, we can determine if there's a cycle by checking if the fast pointer catches up to the slow pointer.

This algorithm works in linear time and constant space, making it an efficient solution to the problem.

Related Interview Questions By Company:

• Intersection Of Two Linked Lists LeetCode
• Verifying An Alien Dictionary LeetCode
• Palindrome Linked List LeetCode

Related Interview Questions By Difficulty:

• Linked List Cycle LeetCode
• Maximum Twin Sum Of A Linked List LeetCode
• Swap Nodes In Pairs LeetCode

Related Interview Questions By Category:

• Subtree Of Another Tree LeetCode
• Split Array Largest Sum LeetCode
• Binary Tree Postorder Traversal LeetCode

Conclusion

In this blog post, we explored the Linked List Cycle problem on LeetCode.

We discussed the problem statement and its constraints.

We then introduced an efficient Python solution using the "Tortoise and Hare" algorithm, explaining how it works step by step.

This algorithm allows us to detect cycles in a linked list with a time complexity of O(n) and a space complexity of O(1).

If you found this explanation helpful, please consider liking and subscribing to support the our platform.

We hope you now have a clear understanding of how to tackle the Linked List Cycle problem efficiently.

If you have any questions or suggestions, feel free to comment below.

For more details and to practice this problem, you can find it on LeetCode at the following link: Linked List Cycle – LeetCode Problem 141.

Happy coding!