leetcode_for_rust/cd0876_middle_of_the_linked_list/
mod.rs

1//! Middle of the Linked List [leetcode: middle_of_the_linked_list](https://leetcode.com/problems/middle-of-the-linked-list/)
2//!
3//! Given a non-empty, singly linked list with head node `head`, return a middle node of linked list.
4//!
5//! If there are two middle nodes, return the second middle node.
6//!
7//! **Example1:**
8//!
9//! ```
10//! Input: [1,2,3,4,5]
11//! Output: Node 3 from this list (Serialization: [3,4,5])
12//! The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).
13//! Note that we returned a ListNode object ans, such that:
14//! ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.
15//! ```
16//!
17//! **Example2:**
18//!
19//! ```
20//! Input: [1,2,3,4,5,6]
21//! Output: Node 4 from this list (Serialization: [4,5,6])
22//! Since the list has two middle nodes with values 3 and 4, we return the second one.
23//! ```
24//!
25//! **Note**
26//!
27//! * The number of nodes in the given list will be between `1` and `100`.
28
29/// # Solutions
30///
31/// # Approach 1: Fast and Slow Pointer
32///
33/// * Time complexity: O(n)
34///
35/// * Space complexity: O(1)
36///
37/// * Runtime: 0ms
38///
39/// Memory: 2.3MB
40///
41/// ```rust
42/// // Definition for singly-linked list.
43/// // #[derive(PartialEq, Eq, Clone, Debug)]
44/// // pub struct ListNode {
45/// //   pub val: i32,
46/// //   pub next: Option<Box<ListNode>>
47/// // }
48/// //
49/// // impl ListNode {
50/// //   #[inline]
51/// //   fn new(val: i32) -> Self {
52/// //     ListNode {
53/// //       next: None,
54/// //       val
55/// //     }
56/// //   }
57/// // }
58///
59/// impl Solution {
60///     pub fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
61///         let mut fast_p = &head;
62///         let mut slow_p = &head;
63///
64///         while fast_p.is_some() && fast_p.as_ref().unwrap().next.is_some() {
65///             slow_p = &slow_p.as_ref().unwrap().next;
66///             fast_p = &fast_p.as_ref().unwrap().next.as_ref().unwrap().next;
67///         }
68///         slow_p.clone()
69///     }
70/// }
71/// ```
72///
73/// # Approach 2: Output of Array
74///
75/// * Time complexity: O(n)
76///
77/// * Space complexity: O(n)
78///
79/// * Runtime: 0ms
80///
81/// Memory: 2.5MB
82///
83/// ```rust
84/// // Definition for singly-linked list.
85/// // #[derive(PartialEq, Eq, Clone, Debug)]
86/// // pub struct ListNode {
87/// //   pub val: i32,
88/// //   pub next: Option<Box<ListNode>>
89/// // }
90/// //
91/// // impl ListNode {
92/// //   #[inline]
93/// //   fn new(val: i32) -> Self {
94/// //     ListNode {
95/// //       next: None,
96/// //       val
97/// //     }
98/// //   }
99/// // }
100///
101/// impl Solution {
102///     pub fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
103///         let mut cur = &head;
104///         let mut node_vec: Vec<Option<Box<ListNode>>> = vec![];
105///
106///         while let Some(node) = cur.as_ref() {
107///             node_vec.push(Some(node.clone()));
108///             cur = &cur.as_ref().unwrap().next;
109///         }
110///
111///         node_vec[node_vec.len() / 2].clone()
112///     }
113/// }
114/// ```
115///
116pub fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
117    let mut fast_p = &head;
118    let mut slow_p = &head;
119
120    while fast_p.is_some() && fast_p.as_ref().unwrap().next.is_some() {
121        slow_p = &slow_p.as_ref().unwrap().next;
122        fast_p = &fast_p.as_ref().unwrap().next.as_ref().unwrap().next;
123    }
124    slow_p.clone()
125}
126
127// Definition for singly-linked list.
128#[derive(Hash, Eq, PartialEq, Debug, Clone)]
129pub struct ListNode {
130    pub val: i32,
131    pub next: Option<Box<ListNode>>
132}
133
134#[allow(dead_code)]
135impl ListNode {
136    #[inline]
137    fn new(val: i32) -> Self {
138        ListNode {
139            next: None,
140            val
141        }
142    }
143}
leetcode_for_rust/cd0876_middle_of_the_linked_list/mod.rs

leetcode_for_rust/cd0876_middle_of_the_linked_list/
mod.rs
