description

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

 

Example 1:

Input: head = [1,1,2]
Output: [1,2]

Example 2:

Input: head = [1,1,2,3,3]
Output: [1,2,3]

 

Constraints:

  • The number of nodes in the list is in the range [0, 300].
  • -100 <= Node.val <= 100
  • The list is guaranteed to be sorted in ascending order.

submission

// 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
//     }
//   }
// }

// iterate through
impl Solution {
    pub fn delete_duplicates(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        // the left pointer
        let mut curr_opt = head.as_mut();
        while let Some(curr) = curr_opt {
            // take next node out since we can't have two mutable
            // reference of the same list
            let mut next_opt = curr.next.take();
            // keep iterate until we reach the end or a different value
            // effectively delete any duplicates of curr node
            while let Some(next) = next_opt.as_mut()
                && next.val == curr.val
            {
                next_opt = next.next.take();
            }
            // we took next out, now insert it back
            curr.next = next_opt;
            // step to next node, which is different value or null
            curr_opt = curr.next.as_mut();
        }
        // we haven't allocate anything, so return the original head
        head
    }
}