DDSA Solutions

3217. Delete Nodes From Linked List Present in Array

MediumView on LeetCode
ArrayHash TableLinked List
Time: O(n + m)
Space: O(m)

Problem Overview

Delete nodes from linked list that appear in a set.

Intuition

Delete nodes from linked list that appear in a set. Scan and skip nodes in the set.

Algorithm

  1. 1Set from nums array. Scan linked list, skip nodes whose val is in set. Return new head.

Common Pitfalls

  • •Handle head deletion carefully. Dummy node simplifies edge case.
3217.cs
C#

// Approach: HashSet of values to remove; traverse list skipping nodes whose value is in the set.
// Time: O(n + m) Space: O(m)

public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

public class Solution
{
    public ListNode ModifiedList(int[] nums, ListNode head)
    {
        ListNode dummy = new ListNode(0, head);
        HashSet<int> numsSet = new HashSet<int>(nums);

        for (ListNode curr = dummy; curr.next != null;)
        {
            if (numsSet.Contains(curr.next.val))
                curr.next = curr.next.next;
            else
                curr = curr.next;
        }

        return dummy.next;
    }
}
Was this solution helpful?

Related Problems