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.
1class ListNode:
2 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6def deleteNodes(head, nums):
7 lookup = set(nums)
8 dummy = ListNode(0)
9 dummy.next = head
10 prev, current = dummy, head
11
12 while current:
13 if current.val in lookup:
14 prev.next = current.next
15 else:
16 prev = current
17 current = current.next
18
19 return dummy.nextA set in Python is used for fast lookup of nodes to be removed. By using a dummy node, the algorithm handles node removal through pointer adjustments effectively.
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).
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
public ListNode DeleteNodes(ListNode head, int[] nums) {
ListNode dummy = new ListNode(0) { next = head };
ListNode prev = dummy, curr = head;
while (curr != null) {
if (IsInArray(curr.val, nums)) {
prev.next = curr.next;
} else {
prev = curr;
}
curr = curr.next;
}
return dummy.next;
}
private bool IsInArray(int val, int[] nums) {
foreach (int n in nums) {
if (n == val) return true;
}
return false;
}
}The C# code employs a helper method IsInArray for checking occurrences in arrays, aligning with the direct manipulation approach to minimize auxiliary space needs.