Leetcode 83. Remove Duplicates from Sorted List

문제 : 83. Remove Duplicates from Sorted List

등급 : Easy

C++로 풀었다면 전혀 고민하지 않았을텐데, Rust는 단순히 포인터 연산을 하려고 해도 소유권을 고려해줘야 하다보니 ListNode를 만드는데서부터 좀 헤매었다.

결국 이번 문제는 Easy임에도 불구하고 Discuss를 좀 참고했고, 재귀와 절차적 접근 방법 각각으로 풀어보게 되었다.

값 자체와, 값을 가리키는 변수의 소유권 & 빌림은 별개로 생각할 수 있다는 점, 그리고 이런 문제에 - 여건이 된다면 - 재귀로 접근해볼 수도 있다는 것을 알게 됨.

// https://leetcode.com/problems/remove-duplicates-from-sorted-list/
// Solved

//Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>
}

impl ListNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        ListNode {
            next: None,
            val
        }
    }

    pub fn generate(nums: Vec<i32>) -> Option<Box<ListNode>> {
        let mut next_node: Option<Box<ListNode>> = None;
        for each in nums.into_iter().rev() {
            let mut cur_node = ListNode::new(each);
            cur_node.next = next_node;
            let mut cur_node = Some(Box::new(cur_node));

            next_node = cur_node;
        }

        next_node
    }
}

// recursive approach
pub(self) mod first_try {
    use crate::remove_duplicates_from_sorted_list::ListNode;

    pub struct Solution;
    impl Solution {
        fn rec(prev_val: i32, cur: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
            if cur.is_none() {
                return None
            }

            let mut cur = cur.unwrap();
            if prev_val == cur.val {
                return Self::rec(prev_val, cur.next)
            }

            cur.next = Self::rec(cur.val, cur.next);
            Some(cur)
        }

        pub fn delete_duplicates(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
            if head.is_none() {
                return None
            }

            let mut head = head.unwrap();
            head.next = Self::rec(head.val, head.next);
            Some(head)
        }
    }
}

// procedural approach
pub(self) mod second_try {
    use crate::remove_duplicates_from_sorted_list::ListNode;
    pub struct Solution;
    impl Solution {
        pub fn delete_duplicates(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
            if head.is_none() {
                return None
            }

            let mut head = head;
            
            let mut prev = head.as_mut();
            while let Some(p) = prev {
                if let Some(cur) = p.next.as_mut() {
                    if p.val == cur.val {
                        p.next = cur.next.take();
                        prev = Some(p);
                        continue
                    }
                }

                prev = p.next.as_mut();
            }

            head
        }
    }
}

#[cfg(test)]
mod tests {
    use crate::remove_duplicates_from_sorted_list::ListNode;

    #[test]
    fn example_first_try() {
        use crate::remove_duplicates_from_sorted_list::first_try::Solution;
        assert_eq!(Solution::delete_duplicates(ListNode::generate(vec![])), ListNode::generate(vec![]));
        assert_eq!(Solution::delete_duplicates(ListNode::generate(vec![1])), ListNode::generate(vec![1]));
        assert_eq!(Solution::delete_duplicates(ListNode::generate(vec![1, 1, 1])), ListNode::generate(vec![1]));
        assert_eq!(Solution::delete_duplicates(ListNode::generate(vec![1, 1, 2])), ListNode::generate(vec![1, 2]));
        assert_eq!(Solution::delete_duplicates(ListNode::generate(vec![1, 1, 2, 3, 3])), ListNode::generate(vec![1, 2, 3]));
    }

    #[test]
    fn example_second_try() {
        use crate::remove_duplicates_from_sorted_list::second_try::Solution;
        assert_eq!(Solution::delete_duplicates(ListNode::generate(vec![])), ListNode::generate(vec![]));
        assert_eq!(Solution::delete_duplicates(ListNode::generate(vec![1])), ListNode::generate(vec![1]));
        assert_eq!(Solution::delete_duplicates(ListNode::generate(vec![1, 1, 1])), ListNode::generate(vec![1]));
        assert_eq!(Solution::delete_duplicates(ListNode::generate(vec![1, 1, 2])), ListNode::generate(vec![1, 2]));
        assert_eq!(Solution::delete_duplicates(ListNode::generate(vec![1, 1, 2, 3, 3])), ListNode::generate(vec![1, 2, 3]));
    }
}