Teaching Kids Programming – Delete Nodes From Linked List Present in Array

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Example 1:
Input: nums = [1,2,3], head = [1,2,3,4,5]
Output: [4,5]
Explanation:
Remove the nodes with values 1, 2, and 3.

Example 2:
Input: nums = [1], head = [1,2,1,2,1,2]
Output: [2,2,2]
Explanation:
Remove the nodes with value 1.

Example 3:
Input: nums = [5], head = [1,2,3,4]
Output: [1,2,3,4]
Explanation:
No node has value 5.

Leetcode 3217: Delete Nodes From Linked List Present in Array

Constraints:
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5
All elements in nums are unique.
The number of nodes in the given list is in the range [1, 105].
1 <= Node.val <= 10^5
The input is generated such that there is at least one node in the linked list that has a value not present in nums.

Hints:
Add all elements of nums into a Set.
Scan the list to check if the current element should be deleted by checking the Set.

Delete Nodes From Linked List Present in Array

We need to convert the list to a (hash) set so that we can lookup an element in the set in O(1) constant time. Then we walk through the linked list, checking if it appears in the set. If it is to delete, we point the previous node’s next to current node’s next.

For example, a linked list A-B-C three nodes, if the middle B is to delete, we just have to point A to C and then remove the B, isn’t that simple?

The trick to implement this would be to have a dummy node, which points to the head, and then after the deletion, we simply remove dummy’s next node. The time complexity is O(N) linear as we need to iterate the linked list (with N nodes).

Of course, we can convert the linked list to array/list, and then do the work/deletion, and then convert it back to a new linked list. This would work, but takes more time and is not the optimal.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def modifiedList(self, nums: List[int], head: Optional[ListNode]) -> Optional[ListNode]:
        if not nums or not head:
            return head
        nums = set(nums)
        dummy = ListNode(-1)
        dummy.next = head
        cur = dummy
        while cur.next:
            if cur.next.val in nums:
                node = cur.next
                cur.next = node.next
                del node
            else:
                cur = cur.next
        return dummy.next

–EOF (The Ultimate Computing & Technology Blog) —