Function 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()
    }
}