3217. Delete Nodes From Linked List Present in Array

MediumView on LeetCode

Array Hash Table Linked List

Time: O(n + m)

Space: O(m)

Intuition

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

Algorithm

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


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