LeetCode Entry

3217. Delete Nodes From Linked List Present in Array

06.09.2024 medium 2024 kotlin rust

Remove nums from a Linked List list

3217. Delete Nodes From Linked List Present in Array medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/726

Problem TLDR

Remove nums from a Linked List #medium #linked_list

Intuition

This is a test of how clean your code can be.

Approach

• use a dummy head to simplify the code
• in Rust it is challenging: better use & references to ListNode objects; use take

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(n)\) for set

Code

    fun modifiedList(nums: IntArray, head: ListNode?): ListNode? {
        val dummy = ListNode(0).apply { next = head }
        val set = nums.toSet(); var curr = dummy
        while (curr.next != null)
            if (curr.next.`val` in set) curr.next = curr.next.next
            else curr = curr.next ?: break
        return dummy.next
    }

    pub fn modified_list(nums: Vec<i32>, head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let set: HashSet<_> = nums.into_iter().collect();
        let mut dummy = ListNode { next: head, val: 0 };
        let mut curr = &mut dummy;
        while let Some(next_box) = curr.next.as_mut() {
            if set.contains(&next_box.val) {
                curr.next = next_box.next.take()
            } else {
                curr = curr.next.as_mut().unwrap()
            }
        }
        dummy.next
    }

    ListNode* modifiedList(vector<int>& nums, ListNode* head) {
        bitset<100001> set; for (int v: nums) set.set(v);
        ListNode* dummy = new ListNode(0); dummy->next = head;
        ListNode* curr = dummy;
        while (curr->next) if (set[curr->next->val])
            curr->next = curr->next->next;
        else curr = curr->next;
        return dummy->next;
    }