Solution 1 - Floyd's Cycle Detection (Two Pointers)
Use a fast pointer that moves two steps and a slow pointer that moves one step. If there is a cycle, they will eventually meet; if the fast pointer reaches None, there is no cycle.
Use a fast pointer that moves two steps and a slow pointer that moves one step. If there is a cycle, they will eventually meet; if the fast pointer reaches None, there is no cycle.
""" 0141.1 - Linked List Cycle - Solution 1 - Floyd's Cycle Detection (Two Pointers) """
#####################################################################################
# Imports
#####################################################################################
from typing import Optional
#####################################################################################
# Classes
#####################################################################################
class ListNode:
"""List Node"""
def __init__(self, x: int):
self.val = x
self.next = None
class Solution:
"""Solution Class"""
def hasCycle(self, head: Optional[ListNode]) -> bool:
"""Linked List Cycle Function"""
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False/** 0141.1 - Linked List Cycle - Solution 1 - Floyd's Cycle Detection (Two Pointers) */
/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class ListNode {
constructor(val) {
this.val = val;
this.next = null;
}
}
class Solution {
/** Linked List Cycle Function */
hasCycle(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
}/** 0141.1 - Linked List Cycle - Solution 1 - Floyd's Cycle Detection (Two Pointers) */
/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class ListNode {
constructor(public val: number, public next: ListNode | null = null) {}
}
class Solution {
/** Linked List Cycle Function */
hasCycle(head: ListNode | null): boolean {
let slow: ListNode | null = head;
let fast: ListNode | null = head;
while (fast && fast.next) {
slow = slow!.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
}// 0141.1 - Linked List Cycle - Solution 1 - Floyd's Cycle Detection (Two Pointers)
package main
/////////////////////////////////////////////////////////////////////////////////////
// Structs
/////////////////////////////////////////////////////////////////////////////////////
type ListNode struct {
Val int
Next *ListNode
}
/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
func hasCycle(head *ListNode) bool {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
return true
}
}
return false
}
func main() {}// 0141.1 - Linked List Cycle - Solution 1 - Floyd's Cycle Detection (Two Pointers)
/////////////////////////////////////////////////////////////////////////////////////
// Structs
/////////////////////////////////////////////////////////////////////////////////////
#[derive(Debug)]
struct ListNode {
val: i32,
next: Option<Box<ListNode>>,
}
struct Solution;
impl Solution {
pub fn has_cycle(head: &Option<Box<ListNode>>) -> bool {
let mut slow = head.as_deref();
let mut fast = head.as_deref();
while let Some(f) = fast {
if f.next.is_none() {
break;
}
slow = slow.and_then(|s| s.next.as_deref());
fast = f.next.as_deref().and_then(|n| n.next.as_deref());
if let (Some(s), Some(f2)) = (slow, fast) {
if std::ptr::eq(s, f2) {
return true;
}
}
}
false
}
}
fn main() {}