876. Middle of the Linked List Easy

1/**
2 * [876] Middle of the Linked List
3 *
4 * Given the head of a singly linked list, return the middle node of the linked list.
5 * If there are two middle nodes, return the second middle node.
6 *  
7 * Example 1:
8 * <img alt="" src="https://assets.leetcode.com/uploads/2021/07/23/lc-midlist1.jpg" style="width: 544px; height: 65px;" />
9 * Input: head = [1,2,3,4,5]
10 * Output: [3,4,5]
11 * Explanation: The middle node of the list is node 3.
12 * 
13 * Example 2:
14 * <img alt="" src="https://assets.leetcode.com/uploads/2021/07/23/lc-midlist2.jpg" style="width: 664px; height: 65px;" />
15 * Input: head = [1,2,3,4,5,6]
16 * Output: [4,5,6]
17 * Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.
18 * 
19 *  
20 * Constraints:
21 * 
22 * The number of nodes in the list is in the range [1, 100].
23 * 1 <= Node.val <= 100
24 * 
25 */
26pub struct Solution {}
27#[allow(unused_imports)]
28use crate::util::linked_list::{ListNode, to_list};
29
30// problem: https://leetcode.com/problems/middle-of-the-linked-list/
31// discuss: https://leetcode.com/problems/middle-of-the-linked-list/discuss/?currentPage=1&orderBy=most_votes&query=
32
33// submission codes start here
34
35// Definition for singly-linked list.
36// #[derive(PartialEq, Eq, Clone, Debug)]
37// pub struct ListNode {
38//   pub val: i32,
39//   pub next: Option<Box<ListNode>>
40// }
41// 
42// impl ListNode {
43//   #[inline]
44//   fn new(val: i32) -> Self {
45//     ListNode {
46//       next: None,
47//       val
48//     }
49//   }
50// }
51impl Solution {
52    pub fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
53        let (mut fast, mut slow)  = (&head, &head);
54        
55        while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
56            slow = &slow.as_ref().unwrap().next;
57            fast = &fast.as_ref().unwrap().next.as_ref().unwrap().next;
58        }
59        slow.clone()
60    }
61}
62
63// submission codes end
64
65#[cfg(test)]
66mod tests {
67    use super::*;
68
69    #[test]
70    fn test_876() {
71        let l = to_list(vec![1,2,3,4,5]);
72        let r = Solution::middle_node(l);
73        assert_eq!(r.unwrap().val, 3)
74    }
75}
76