Practice/Google/Leetcode 3217. Delete Nodes From Linked List Present in Array

Leetcode 3217. Delete Nodes From Linked List Present in Array

CodingOptional

Problem

You are given an array of integers nums and the head of a singly linked list. Your task is to remove all nodes from the linked list whose values appear in the array nums, and return the head of the modified linked list.

The linked list should maintain its original order after removing the specified nodes. If all nodes are removed, return null.

Requirements

1. Remove all nodes whose values exist in the nums array
2. Maintain the relative order of remaining nodes
3. Return the new head of the modified linked list
4. Handle cases where the head node itself needs to be removed
5. Handle cases where all nodes need to be removed

Constraints

• 1 ≤ nums.length ≤ 105
• 1 ≤ nums[i] ≤ 105
• The number of nodes in the linked list is in the range [1, 105]
• 1 ≤ Node.val ≤ 105
• All values in nums are unique
• You should aim for O(n + m) time complexity where n is the length of the linked list and m is the length of the array

Examples

Example 1:

Input: nums = [1, 2, 3], head = [1, 2, 3, 4, 5] Output: [4, 5] Explanation: The nodes with values 1, 2, and 3 are present in the nums array, so they are removed. Only nodes with values 4 and 5 remain.

Example 2:

Input: nums = [5], head = [5, 10, 15, 20] Output: [10, 15, 20] Explanation: The head node with value 5 is removed, and the node with value 10 becomes the new head.

Example 3:

Input: nums = [1, 2, 3], head = [1, 2, 3] Output: null Explanation: All nodes in the linked list have values that appear in the nums array, so all nodes are removed.

Example 4:

Input: nums = [10, 20], head = [1, 2, 3, 4] Output: [1, 2, 3, 4] Explanation: None of the node values appear in the nums array, so the linked list remains unchanged.