Linked List Cycle
Given the head of a linked list, write a function hasCycle to determine if the linked list has a cycle in it. A linked list is said to have a cycle if a node's next pointer points to a previous node in the list, forming a loop. Return true if there is a cycle, otherwise return false.
Example
Can you come up with a solution with O(n) time complexity?
Can you come up with a solution with O(1) space complexity?
Our solution detects whether a linked list contains a cycle by employing the Floyd's Tortoise and Hare algorithm. This algorithm uses two pointers, slow and fast, which traverse the linked list at different speeds.
- Initialization: Both
slowandfastpointers start at the head of the linked list. - Traversal:
- Slow Pointer: Moves one step at a time (
slow = slow->next). - Fast Pointer: Moves two steps at a time (
fast = fast->next->next).
- Slow Pointer: Moves one step at a time (
- Detection:
- If at any point the
slowpointer andfastpointer meet, it indicates the presence of a cycle in the linked list. This is because thefastpointer will loop around and eventually catch up with theslowpointer if a cycle exists. - If the
fastpointer reaches the end of the list (fast == nullptrorfast->next == nullptr), then there is no cycle in the list.
- If at any point the
The algorithm is efficient as it only requires a single pass through the list with constant space complexity. It is straightforward and avoids the need for extra data structures.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def has_cycle(head: ListNode) -> bool:
slow = head
fast = head
while fast and fast.next:
slow = slow.next # Move slow pointer by 1 step
fast = fast.next.next # Move fast pointer by 2 steps
if slow == fast:
return True # A cycle is detected
return False # No cycle detectedTime Complexity: The solution has a time complexity of O(n), where n is the number of nodes in the linked list. This is because the slow and fast pointers will traverse the list at most once each, making the traversal efficient.
Space Complexity: The solution has a space complexity of O(1) since it uses only two pointers and does not require additional space proportional to the input size. This makes the algorithm both space and time efficient.
Check out our lesson on the tortoise & hare approach to learn more about what it is and how to use it!
I was able to answer this question and the follow-up questions as well