1600 LCs

Happy to complete my 1600th LeetCode problem. I picked a Medium one to mark this milestone: remove from a linked list elements in a given array. Use a hash set to store the elements of the array for quick look-up. Deal with the head of the list separately, then the body. Code is down below, cheers, ACC.

Delete Nodes From Linked List Present in Array - LeetCode

ou are given an array of integers nums and the head of a linked list. Return the head of the modified linked list after removing all nodes from the linked list that have a value that exists in nums.

 

Example 1:

Input: nums = [1,2,3], head = [1,2,3,4,5]

Output: [4,5]

Explanation:

Remove the nodes with values 1, 2, and 3.

Example 2:

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

Output: [2,2,2]

Explanation:

Remove the nodes with value 1.

Example 3:

Input: nums = [5], head = [1,2,3,4]

Output: [1,2,3,4]

Explanation:

No node has value 5.

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105
• All elements in nums are unique.
• The number of nodes in the given list is in the range [1, 105].
• 1 <= Node.val <= 105
• The input is generated such that there is at least one node in the linked list that has a value not present in nums.

/**
 * Definition for singly-linked list.
 * 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) {
        if (head == null) return head;

        HashSet uniqueElements = new HashSet();

        foreach (int n in nums)
            if (!uniqueElements.Contains(n)) uniqueElements.Add(n);

        //Head
        while (head != null && uniqueElements.Contains(head.val))
            head = head.next;

        if (head == null) return head;

        //Body
        ListNode retVal = head;
        while (head.next != null)
        {
            if (uniqueElements.Contains(head.next.val))
            {
                head.next = head.next.next;
            }
            else
            {
                head = head.next;
            }
        }

        return retVal;
    }
}