leetcode/
remove_duplicates_from_sorted_list_ii.rs

1//! # 82. 删除排序链表中的重复元素 II
2//!
3//! 难度 中等
4//!
5//! 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
6//!
7//! ## 示例 1:
8//!
9//! ```text
10//! 输入: 1->2->3->3->4->4->5
11//! 输出: 1->2->5
12//! ```
13//!
14//! ## 示例 2:
15//!
16//! ```text
17//! 输入: 1->1->1->2->3
18//! 输出: 2->3
19//! ```
20//!
21//! See [leetcode](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/)
22//!
23
24use crate::ListNode;
25
26pub struct Solution;
27
28impl Solution {
29    pub fn delete_duplicates(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
30        if head.is_none() || head.as_ref().unwrap().next.is_none() {
31            return head;
32        }
33
34        if head.as_ref().unwrap().val == head.as_ref().unwrap().next.as_ref().unwrap().val {
35            while head.is_some() && head.as_mut().unwrap().next.is_some() && head.as_mut().unwrap().next.as_mut().unwrap().val == head.as_mut().unwrap().val {
36                head = head.as_mut().unwrap().next.take();
37            }
38            return Solution::delete_duplicates(head.and_then(|mut head| head.next.take()));
39        } else {
40            head.as_mut().unwrap().next = Solution::delete_duplicates(head.as_mut().unwrap().next.take());
41            head
42        }
43    }
44
45    pub fn delete_duplicates_2(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
46        head.and_then(|mut head| {
47            let mut next = head.next.take();
48            if next.is_none() {
49                return head.into();
50            }
51
52            if next.as_ref().unwrap().val == head.val {
53                while next.is_some() && head.val == next.as_ref().unwrap().val {
54                    head = next.unwrap();
55                    next = head.next.take();
56                }
57                Solution::delete_duplicates_2(next)
58            } else {
59                head.next = Solution::delete_duplicates_2(next);
60                head.into()
61            }
62        })
63    }
64}
65
66#[cfg(test)]
67mod tests {
68    use super::*;
69    use crate::list;
70
71    #[test]
72    fn test() {
73        let t = |t| ListNode::into_vec(Solution::delete_duplicates(t));
74        let t2 = |t| ListNode::into_vec(Solution::delete_duplicates_2(t));
75        let cases = vec![
76            (vec![1,2,5], list![1,2,3,3,4,4,5]),
77            (vec![2,3], list![1,1,1,2,3]),
78            (vec![], list![]),
79        ];
80
81        for (expect, input) in cases {
82            assert_eq!(expect, t(input.clone()));
83            assert_eq!(expect, t2(input));
84        }
85    }
86}
leetcode/remove_duplicates_from_sorted_list_ii.rs

leetcode/
remove_duplicates_from_sorted_list_ii.rs
