easyLinked ListPattern: Slow & Fast Pointer
LinkedList Cycle Detection Solution
Problem Statement
Given the head of a singly linked list, determine if the linked list has a cycle in it. A cycle exists if any node in the list can be reached again by continuously following the next pointer. If there is a cycle, return true. Otherwise, return false.
Examples
Example 1:
Input:Head points to a list where node 3 points back to node 1. (e.g., 1 -> 2 -> 3 -> 1)
Output:false
Explanation: The linked list has a cycle because the node with value 3 points back to the node with value 1.
Example 2:
Input:Head points to a list where node 2 points back to node 0. (e.g., 0 -> 1 -> 2 -> 0)
Output:false
Explanation: The linked list has a cycle because the node with value 2 points back to the node with value 0.
Example 3:
Input:Head points to a list with no cycle. (e.g., 0 -> 1 -> 2)
Output:false
Explanation: The linked list does not have a cycle as the last node's next pointer is null.
Constraints
- The number of nodes in the list can be between 0 and 10^5.
- The value of each node is between -10^5 and 10^5.
- The `next` pointer of each node is either `null` or points to an index in the array.
- The list can be empty.
Time: O(N) Space: O(1)
Utilize the 'tortoise and hare' approach with two pointers: a slow pointer that moves one step at a time and a fast pointer that moves two steps at a time. If the list has a cycle, the fast pointer will eventually catch up to the slow pointer. If the fast pointer reaches the end of the list (null), then there is no cycle.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
from typing import Optional
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if not head or not head.next:
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