[−][src]Function leetcode_for_rust::cd0876_middle_of_the_linked_list::middle_node
pub fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>>
Solutions
Approach 1: Fast and Slow Pointer
-
Time complexity: O(n)
-
Space complexity: O(1)
-
Runtime: 0ms
Memory: 2.3MB
// Definition for singly-linked list. // #[derive(PartialEq, Eq, Clone, Debug)] // 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 middle_node(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; } slow_p.clone() } }
Approach 2: Output of Array
-
Time complexity: O(n)
-
Space complexity: O(n)
-
Runtime: 0ms
Memory: 2.5MB
// Definition for singly-linked list. // #[derive(PartialEq, Eq, Clone, Debug)] // 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 middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> { let mut cur = &head; let mut node_vec: Vec<Option<Box<ListNode>>> = vec![]; while let Some(node) = cur.as_ref() { node_vec.push(Some(node.clone())); cur = &cur.as_ref().unwrap().next; } node_vec[node_vec.len() / 2].clone() } }