Remove duplicates from an unsorted linked list

Hash Table Linked List

75.6% acceptance

Mar 31, 2026

408

Given the head of a linked list, find all the values that appear more than once in the list and delete the nodes that have any of those values. Return the linked list after the deletions.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

// 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
//     }
//   }
// }
use std::collections::HashMap;

impl Solution {
  pub fn delete_duplicates_unsorted(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut freq = HashMap::new();
    let mut curr = &head;
    while let Some(node) = curr {
      *freq.entry(node.val).or_insert(0) += 1;
      curr = &node.next;
    }
    let mut dummy = Box::new(ListNode::new(0));
    dummy.next = head;
    let mut curr = &mut dummy;
    while curr.next.is_some() {
      if freq[&curr.next.as_ref().unwrap().val] > 1 {
        curr.next = curr.next.as_mut().unwrap().next.take();
      } else {
        curr = curr.next.as_mut().unwrap();
      }
    }
    dummy.next
  }
}