Sponsored
Sponsored
This approach uses a set for fast lookup of values that need to be removed from the linked list. By iterating through the linked list and checking if each node's value is in the set, we can efficiently determine which nodes to skip and which to keep.
Time Complexity: O(N + M), where N is the length of the linked list and M is the size of nums.
Space Complexity: O(M), where M is the size of nums.
1import java.util.HashSet;
2import java.util.Set;
3
4class ListNode {
5 int val;
6 ListNode next;
7 ListNode(int x) { val = x; }
8}
9
10public class Solution {
11 public ListNode deleteNodes(ListNode head, int[] nums) {
12 Set<Integer> set = new HashSet<>();
13 for (int num : nums) {
14 set.add(num);
15 }
16
17 ListNode dummy = new ListNode(0);
18 dummy.next = head;
19 ListNode prev = dummy, current = head;
20
21 while (current != null) {
22 if (set.contains(current.val)) {
23 prev.next = current.next;
24 } else {
25 prev = current;
26 }
27 current = current.next;
28 }
29 return dummy.next;
30 }
31}In Java, a HashSet enables O(1) average time complexity for lookups. We manage the removal process by keeping track of the previous node using a dummy node and selectively adjusting pointers as necessary.
This approach leverages a two-pointer technique where the result is constructed in-place. Although it doesn't require extra storage for the set, it does involve modifications that make subsequent operations more complex in favor of reducing space usage.
Time Complexity: O(N * M), where N is the length of the linked list and M is the size of nums.
Space Complexity: O(1).
The Python code utilizes list membership checking instead of a hash structure, achieving in-place node management without additional memory allocations for lookup.