Jobs

Interviews

Discussions

Delete Nodes From Linked List Present in Array

Medium

Asked by:

23 views

Topics:

Linked ListsArrays

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.

Constraints:

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

Try coding it in LeetCode

Delete Nodes From Linked List Present in Array

Medium

Asked by:

23 views

Topics:

Linked ListsArrays

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.

Constraints:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the values in the linked list and the array of nodes to delete contain duplicates?
What is the expected behavior if the linked list is empty or if the array of nodes to delete is empty?
Is the linked list singly or doubly linked?
What is the data type of the values stored in the linked list nodes and the array of nodes to delete (e.g., integers, strings)? Are there any constraints on the range of these values?
Should I modify the original linked list in place, or should I return a new linked list?

Brute Force Solution

Approach

Imagine you have a train of linked boxcars, and you have a list of specific boxcar numbers to remove from the train. The brute force way checks each boxcar individually to see if it is on the list of boxcars we must remove.

Here's how the algorithm would work step-by-step:

Start with the first boxcar in the train.
Look at your list of boxcars to remove and check if the current boxcar's number is on that list.
If it is on the list, remove the boxcar from the train.
If it is not on the list, keep the boxcar in the train and move to the next boxcar.
Repeat this process for every boxcar in the train, one at a time, checking against the list each time.
After checking every boxcar in the train, you will have the final train with only the desired boxcars remaining.

Code Implementation

def delete_nodes_from_linked_list(head, nodes_to_delete):    current_node = head
    previous_node = None

    while current_node:
        # Check if the current node's value is in the delete list
        if current_node.val in nodes_to_delete:

            # Handle the case where the node to delete is the head
            if previous_node is None:
                head = current_node.next
            else:
                previous_node.next = current_node.next

            current_node = current_node.next
        else:
            previous_node = current_node
            current_node = current_node.next

    return head

Big(O) Analysis

Time Complexity

O(n*m) – The algorithm iterates through each of the 'n' nodes in the linked list. For each node, it checks if the node's value is present in the array of 'm' nodes to be deleted. This involves iterating through the array of nodes to be deleted, resulting in 'm' comparisons for each node in the linked list. Therefore, the time complexity is proportional to n * m.

Space Complexity

O(1) – The provided solution iterates through the linked list, checking each node against a list of nodes to delete. While the plain English explanation does not provide specific implementation details, the steps described do not necessitate any auxiliary data structures. No additional lists, maps, or significant variables beyond the current node being processed are created. Thus, the space usage remains constant regardless of the size of the linked list N or the list of nodes to delete, implying a space complexity of O(1).

Optimal Solution

Approach

We want to remove specific nodes from a linked list, where the nodes to remove are identified by their values which are present in an array. The efficient way involves checking each node in the linked list once and removing it if its value is in the array. This avoids repeatedly searching the list or array.

Here's how the algorithm would work step-by-step:

First, create a quick way to check if a value exists in the array of values we want to delete. Think of it like creating a set, which allows for very fast lookups.
Start at the beginning of the linked list.
Look at the value of the current node. Is it in our set of values to delete?
If the current node's value is in the set, we need to remove it. Update the previous node to point to the next node, effectively skipping over the current node.
If the current node's value is NOT in the set, move the 'previous' marker to the current node. We keep track of the 'previous' node so we can easily remove nodes when necessary.
Move to the next node in the linked list and repeat steps 3-5 until the end of the list is reached.
Be careful when handling the head of the linked list. If the head needs to be deleted, update the head to the next node in the list.

Code Implementation

class ListNode:
    def __init__(self, value):
        self.value = value
        self.next = None

def delete_nodes(head, values_to_delete):
    values_to_delete_set = set(values_to_delete)

    # Handle the case where the head itself needs to be deleted.
    while head and head.value in values_to_delete_set:
        head = head.next

    if not head:
        return None

    previous_node = head
    current_node = head.next

    while current_node:
        # Check if the current node's value is in the set of values to delete.
        if current_node.value in values_to_delete_set:
            # Remove the current node by updating the previous node's next pointer.
            previous_node.next = current_node.next
            current_node = current_node.next
        else:
            # Move previous node forward.
            previous_node = current_node
            current_node = current_node.next

    return head

Big(O) Analysis

Time Complexity

O(n + m) – The algorithm iterates through the linked list of size 'n' once. Before this iteration, it converts the array of size 'm' (containing values to delete) into a set. Creating the set takes O(m) time. The linked list traversal takes O(n) time, where for each node it performs a constant-time lookup in the set to determine if it should be deleted. Therefore, the total time complexity is O(n + m).

Space Complexity

O(M) – The algorithm uses a set to store the values from the array that need to be deleted from the linked list. The size of this set directly corresponds to the number of elements, M, in the input array of values to delete. The space used by the set is independent of the linked list size, denoted as N. Therefore, the auxiliary space is proportional to the size of the array, M, resulting in O(M) space complexity.

Edge Cases

Case	How to Handle
Empty linked list	Return null immediately as there are no nodes to delete.
Null linked list	Return null immediately as there is no list to operate on.
Empty array of values to delete	Return the original linked list as no nodes need to be deleted.
Null array of values to delete	Return the original linked list as no nodes need to be deleted.
Linked list contains duplicate values that are also in the delete array	Ensure all occurrences of these duplicate values are deleted from the linked list.
Delete array contains values not present in the linked list	The algorithm should safely ignore these values without errors.
All nodes in the linked list need to be deleted	Return null, indicating an empty linked list.
Head node's value is in the delete array	Update the head pointer correctly to the next valid node after deletion.

Empty linked list

How to Handle:

Return null immediately as there are no nodes to delete.

Null linked list

How to Handle:

Return null immediately as there is no list to operate on.

Empty array of values to delete

How to Handle:

Return the original linked list as no nodes need to be deleted.

Null array of values to delete

How to Handle:

Return the original linked list as no nodes need to be deleted.

Linked list contains duplicate values that are also in the delete array

How to Handle:

Ensure all occurrences of these duplicate values are deleted from the linked list.

Delete array contains values not present in the linked list

How to Handle:

The algorithm should safely ignore these values without errors.

All nodes in the linked list need to be deleted

How to Handle:

Return null, indicating an empty linked list.

Head node's value is in the delete array

How to Handle:

Update the head pointer correctly to the next valid node after deletion.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the values in the linked list and the array of nodes to delete contain duplicates?
What is the expected behavior if the linked list is empty or if the array of nodes to delete is empty?
Is the linked list singly or doubly linked?
What is the data type of the values stored in the linked list nodes and the array of nodes to delete (e.g., integers, strings)? Are there any constraints on the range of these values?
Should I modify the original linked list in place, or should I return a new linked list?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the first boxcar in the train.
Look at your list of boxcars to remove and check if the current boxcar's number is on that list.
If it is on the list, remove the boxcar from the train.
If it is not on the list, keep the boxcar in the train and move to the next boxcar.
Repeat this process for every boxcar in the train, one at a time, checking against the list each time.
After checking every boxcar in the train, you will have the final train with only the desired boxcars remaining.

Code Implementation

def delete_nodes_from_linked_list(head, nodes_to_delete):    current_node = head
    previous_node = None

    while current_node:
        # Check if the current node's value is in the delete list
        if current_node.val in nodes_to_delete:

            # Handle the case where the node to delete is the head
            if previous_node is None:
                head = current_node.next
            else:
                previous_node.next = current_node.next

            current_node = current_node.next
        else:
            previous_node = current_node
            current_node = current_node.next

    return head

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, create a quick way to check if a value exists in the array of values we want to delete. Think of it like creating a set, which allows for very fast lookups.
Start at the beginning of the linked list.
Look at the value of the current node. Is it in our set of values to delete?
If the current node's value is in the set, we need to remove it. Update the previous node to point to the next node, effectively skipping over the current node.
If the current node's value is NOT in the set, move the 'previous' marker to the current node. We keep track of the 'previous' node so we can easily remove nodes when necessary.
Move to the next node in the linked list and repeat steps 3-5 until the end of the list is reached.
Be careful when handling the head of the linked list. If the head needs to be deleted, update the head to the next node in the list.

Code Implementation

class ListNode:
    def __init__(self, value):
        self.value = value
        self.next = None

def delete_nodes(head, values_to_delete):
    values_to_delete_set = set(values_to_delete)

    # Handle the case where the head itself needs to be deleted.
    while head and head.value in values_to_delete_set:
        head = head.next

    if not head:
        return None

    previous_node = head
    current_node = head.next

    while current_node:
        # Check if the current node's value is in the set of values to delete.
        if current_node.value in values_to_delete_set:
            # Remove the current node by updating the previous node's next pointer.
            previous_node.next = current_node.next
            current_node = current_node.next
        else:
            # Move previous node forward.
            previous_node = current_node
            current_node = current_node.next

    return head

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty linked list	Return null immediately as there are no nodes to delete.
Null linked list	Return null immediately as there is no list to operate on.
Empty array of values to delete	Return the original linked list as no nodes need to be deleted.
Null array of values to delete	Return the original linked list as no nodes need to be deleted.
Linked list contains duplicate values that are also in the delete array	Ensure all occurrences of these duplicate values are deleted from the linked list.
Delete array contains values not present in the linked list	The algorithm should safely ignore these values without errors.
All nodes in the linked list need to be deleted	Return null, indicating an empty linked list.
Head node's value is in the delete array	Update the head pointer correctly to the next valid node after deletion.

Empty linked list

How to Handle:

Return null immediately as there are no nodes to delete.

Null linked list

How to Handle:

Return null immediately as there is no list to operate on.

Empty array of values to delete

How to Handle:

Return the original linked list as no nodes need to be deleted.

Null array of values to delete

How to Handle:

Return the original linked list as no nodes need to be deleted.

Linked list contains duplicate values that are also in the delete array

How to Handle:

Ensure all occurrences of these duplicate values are deleted from the linked list.

Delete array contains values not present in the linked list

How to Handle:

The algorithm should safely ignore these values without errors.

All nodes in the linked list need to be deleted

How to Handle:

Return null, indicating an empty linked list.

Head node's value is in the delete array

How to Handle:

Update the head pointer correctly to the next valid node after deletion.