<p>You are given an array of integers <code>nums</code> and the <code>head</code> of a linked list. Return the <code>head</code> of the modified linked list after <strong>removing</strong> all nodes from the linked list that have a value that exists in <code>nums</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,2,3], head = [1,2,3,4,5]</span></p>

<p><strong>Output:</strong> <span class="example-io">[4,5]</span></p>

<p><strong>Explanation:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2024/06/11/linkedlistexample0.png" style="width: 400px; height: 66px;" /></strong></p>

<p>Remove the nodes with values 1, 2, and 3.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1], head = [1,2,1,2,1,2]</span></p>

<p><strong>Output:</strong> <span class="example-io">[2,2,2]</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/06/11/linkedlistexample1.png" style="height: 62px; width: 450px;" /></p>

<p>Remove the nodes with value 1.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [5], head = [1,2,3,4]</span></p>

<p><strong>Output:</strong> <span class="example-io">[1,2,3,4]</span></p>

<p><strong>Explanation:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2024/06/11/linkedlistexample2.png" style="width: 400px; height: 83px;" /></strong></p>

<p>No node has value 5.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>
	<li>All elements in <code>nums</code> are unique.</li>
	<li>The number of nodes in the given list is in the range <code>[1, 10<sup>5</sup>]</code>.</li>
	<li><code>1 &lt;= Node.val &lt;= 10<sup>5</sup></code></li>
	<li>The input is generated such that there is at least one node in the linked list that has a value not present in <code>nums</code>.</li>
</ul>

from typing import List, Optional

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution1:
    # T.C. - O(n * n) with optimised operations
    def modifiedList(self, nums: List[int], head: Optional[ListNode]) -> Optional[ListNode]:

        # nnums = set(nums) # make set for 'in' operator to get T.C. - O(1)

        nnums = {None} # unordered set
        for num in nums:
            nnums.add(num)

        isFirstTime = False
        new_head = None
        new_node = None
        node = head

        while node:
            val = node.val

            if not val in nnums: # have to delete ; O(n) #TODO: we can use binary-search: O(logN)
                if not isFirstTime:
                    new_head = ListNode(node.val)
                    isFirstTime = True
                    new_node = new_head
                else:
                    tnn = ListNode(node.val)
                    new_node.next = tnn
                    new_node = tnn
            node = node.next
        
        return new_head


"""
    # If we use binary-search then T.C. - O(N * logN)
"""


class Solution:
    """
        Here, T.C. - O(N) cause we will use hash table.
    """
    def modifiedList(self, nums: List[int], head: Optional[ListNode]) -> Optional[ListNode]:
        max_val = -1
        for num in nums:
            max_val = max(max_val, num)
        
        freq = [False] * (max_val + 1)
        for num in nums:
            freq[num] = True # this num exists - index is the num itself
        
        temp = ListNode()
        current = temp
        
        while head:
            if head.val >= len(freq) or freq[head.val]==False: # this head.val is missing in the nums list, have to keep
                current.next = head
                current = current.next
            head = head.next
        
        current.next = None
        return temp.next # here, the first node has no value, val=0 but the next has the acutual first element/node
        
if __name__=="__main__":
    obj = Solution()
    node5 = ListNode(5)
    node4 = ListNode(4, node5)
    node3 = ListNode(3, node4)
    node2 = ListNode(2, node3)
    node1 = ListNode(1, node2)
    
    head = node1
    nums = [1,2,3]
    
    new_head = obj.modifiedList(nums, head)
    print("================================================")
    while new_head:
        print(new_head.val)
        new_head = new_head.next
50931