Function leetcode_for_rust::cd0141_linked_list_cycle::has_cycle

pub fn has_cycle(head: Option<Box<ListNode>>) -> bool

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
    }
}