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).
The Python code utilizes list membership checking instead of a hash structure, achieving in-place node management without additional memory allocations for lookup.