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