lunaris_engine 0.1.0

A collection of efficient algorithms implemented in Rust for real-world projects.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

//! Detect Cycle in Singly Linked list (Floyd's Tortoise and Hare, Generic, Production-Grade)
//!
//! Detects if a singly linked list has a cycle.
//!
//! # Type Parameters
//! * `T`: Value type. Must implement `Clone`.
//!
//! # Example
//! ```rust
//! use lunaris_engine::linked_list::detect_cycle::*;
//! use lunaris_engine::linked_list::singly_linked_list::ListNode;
//! let mut head = Some(Box::new(ListNode::new(1)));
//! head.as_mut().unwrap().next = Some(Box::new(ListNode::new(2)));
//! assert!(!has_cycle(&head));
//! ```
use crate::linked_list::singly_linked_list::ListNode;

pub fn has_cycle<T: Clone>(head: &Option<Box<ListNode<T>>>) -> bool {
    let mut slow = head.as_ref().map(|n| &**n);
    let mut fast = head.as_ref().map(|n| &**n);
    while let (Some(s), Some(f)) = (slow, fast) {
        slow = s.next.as_deref();
        fast = f
            .next
            .as_ref()
            .and_then(|n| n.next.as_deref());
        if let (Some(s_ptr), Some(f_ptr)) = (slow, fast)
            && std::ptr::eq(s_ptr, f_ptr) {
                return true;
            }
    }
    false
}