pub fn has_cycle(head: Option<Box<ListNode>>) -> bool
Expand description
§Solutions
§Approach 1: Hash Table
-
Time complexity: O(n)
-
Space complexity: O(n)
-
Runtime: 0ms
Memory: 2.4MB
// Definition for singly-linked list.
// #[derive(Hash, Eq, PartialEq, Debug, Clone)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
use std::collections::HashSet;
impl Solution {
pub fn has_cycle(mut head: Option<Box<ListNode>>) -> bool {
let mut vikings = HashSet::new();
let mut cur = &mut head;
while let Some(cur_mut) = cur.as_mut() {
let cur_mut = cur.as_mut().unwrap();
if vikings.contains(cur_mut) {
return true;
} else {
vikings.insert(cur_mut.clone());
}
cur = &mut cur_mut.next;
}
false
}
}
§Approach 2: Fast and Slow Pointer
-
Time complexity: O(n)
-
Space complexity: O(1)
-
Runtime: 0ms
Memory: 2.4MB
// Definition for singly-linked list.
// #[derive(Hash, Eq, PartialEq, Debug, Clone)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn has_cycle(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut fast_p = &head;
let mut slow_p = &head;
while fast_p.is_some() && fast_p.as_ref().unwrap().next.is_some() {
slow_p = &slow_p.as_ref().unwrap().next;
fast_p = &fast_p.as_ref().unwrap().next.as_ref().unwrap().next;
if slow_p == fast_p { return true; }
}
false
}
}