leetcode/
mid_list.rs

1//! # 876. 链表的中间结点
2//!
3//! 难度 简单
4//!
5//! 给定一个头结点为 head 的非空单链表，返回链表的中间结点。
6//!
7//! 如果有两个中间结点，则返回第二个中间结点。
8//!
9//! ## 示例 1：
10//!
11//! ```text
12//! 输入：[1,2,3,4,5]
13//! 输出：此列表中的结点 3 (序列化形式：[3,4,5])
14//! 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
15//! 注意，我们返回了一个 ListNode 类型的对象 ans，这样：
16//! ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
17//! ```
18//!
19//! ## 示例 2：
20//!
21//! ```text
22//! 输入：[1,2,3,4,5,6]
23//! 输出：此列表中的结点 4 (序列化形式：[4,5,6])
24//! 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
25//! ```
26//!
27//!
28//! ## 提示：
29//!
30//! 给定链表的结点数介于 1 和 100 之间。
31//!
32//! See [leetcode](https://leetcode-cn.com/problems/middle-of-the-linked-list/)
33
34use crate::ListNode;
35
36/// 快慢指针
37///
38/// <del>但 Rust 中对于一个值不能有两个 mut 的引用，所以可以裸指针。 因为在一个函数里操作，可以保证是安全的。</del>
39/// 这里返回可以 Clone...
40pub struct Solution;
41
42impl Solution {
43
44    pub fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
45        let mut slow = &head;
46        let mut fast = &head;
47
48        while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
49            slow = &slow.as_ref().unwrap().next;
50            fast = &fast.as_ref().unwrap().next.as_ref().unwrap().next;
51        }
52        slow.clone()
53    }
54}
55
56#[cfg(test)]
57mod tests {
58    use super::*;
59    use crate::list;
60
61    #[test]
62    fn test() {
63        let t = |v| ListNode::into_vec(Solution::middle_node(v));
64        assert_eq!(vec![3,4,5], t(list![1,2,3,4,5]));
65        assert_eq!(vec![4,5,6], t(list![1,2,3,4,5,6]));
66        assert_eq!(vec![2], t(list![2]));
67        assert_eq!(vec![0i32;0], t(list![]));
68    }
69}
leetcode/mid_list.rs

leetcode/
mid_list.rs
