Jobs

Interviews

Discussions

Remove Linked List Elements

Easy

Asked by:

18 views

Topics:

Linked Lists

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

Example 1:

Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]

Example 2:

Input: head = [], val = 1
Output: []

Example 3:

Input: head = [7,7,7,7], val = 7
Output: []

Constraints:

The number of nodes in the list is in the range [0, 10⁴].
1 <= Node.val <= 50
0 <= val <= 50

Remove Linked List Elements

Easy

Asked by:

18 views

Topics:

Linked Lists

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

Example 1:

Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]

Example 2:

Input: head = [], val = 1
Output: []

Example 3:

Input: head = [7,7,7,7], val = 7
Output: []

Constraints:

The number of nodes in the list is in the range [0, 10⁴].
1 <= Node.val <= 50
0 <= val <= 50

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 linked list be empty (head is null)?
What is the range of values for nodes in the linked list and for the 'val' we need to remove?
If all nodes in the list have the value 'val', should I return null?
Are the node values integers?
Is it acceptable to modify the original linked list in place, or do I need to create a new one?

Brute Force Solution

Approach

Imagine you have a chain of connected items, and you want to remove specific unwanted items from this chain. The brute force method involves going through the chain and, for each item, checking if it needs to be removed. If it does, we take it out.

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

Start at the beginning of the chain.
Look at the first item.
Is this the item you want to remove?
If yes, take it out of the chain. You might have to reconnect the items on either side of the removed item.
If no, move to the next item.
Repeat steps 2-5 for every item in the chain.

Code Implementation

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

def remove_linked_list_elements_brute_force(head, value):
    current_node = head
    previous_node = None

    while current_node:
        # Check if the current node's value matches the value to remove
        if current_node.val == value:
            if previous_node:
                # Bypass the current node to remove it
                previous_node.next = current_node.next

            else:
                # If the head node needs to be removed, update the head
                head = current_node.next

            current_node = current_node.next
        else:
            # Move both pointers forward
            previous_node = current_node
            current_node = current_node.next

    return head

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the linked list of n nodes once. For each node, it checks if its value equals the value to be removed. If it does, the node is removed by updating the next pointer of the previous node. This process visits each node at most once, resulting in a time complexity of O(n), where n is the number of nodes in the linked list. The operations inside the loop (comparison and pointer manipulation) take constant time.

Space Complexity

O(1) – The provided explanation describes an iterative in-place modification of the linked list. It only involves traversing the list and potentially reconnecting nodes by updating pointers. No auxiliary data structures like arrays, hash maps, or additional lists are used. Thus, the space required remains constant, independent of the number of nodes (N) in the linked list. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The trick to efficiently removing elements from a linked list is to carefully step through the list and make adjustments as you go. We'll use a 'helper' to keep track of where we are and make changes safely, especially at the beginning of the list. This helps us avoid accidentally losing parts of the list.

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

First, imagine a 'helper' pointing right before the very start of your list. This makes it easier to change the beginning of the list if needed.
Move the 'helper' to the beginning of the real list.
Check if the very first item in the list should be removed. If it should, update the beginning of the list to skip over this unwanted item.
Now, go through the list one item at a time.
For each item, check if it should be removed.
If it should be removed, carefully 'unlink' it from the list. That means changing what the previous item points to, so it skips over the item being removed. The helper will not move.
If the current item should NOT be removed, simply move the 'helper' forward to the next item.
Keep going until you've checked every item in the list.
Finally, return the (potentially updated) beginning of the list.

Code Implementation

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

def removeElements(head: ListNode, value: int) -> ListNode:
    dummy_node = ListNode(0)
    dummy_node.next = head
    current_node = head
    previous_node = dummy_node

    # Use a helper to handle the head removal case elegantly.
    while current_node:
        if current_node.val == value:

            # Remove the node by updating the previous node's next pointer.
            previous_node.next = current_node.next
            current_node = current_node.next
        else:

            # Advance both pointers only if no removal is needed.
            previous_node = current_node
            current_node = current_node.next

    # The dummy node's next is now the new head.
    return dummy_node.next

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the linked list once, where n is the number of nodes in the list. During this single pass, each node is examined to determine if its value matches the value to be removed. The 'helper' pointer advances through the list, performing a constant amount of work (comparison and potentially a pointer reassignment) at each node. Therefore, the time complexity is directly proportional to the number of nodes, resulting in O(n).

Space Complexity

O(1) – The algorithm uses a 'helper' which can be considered a pointer to a node in the list, requiring constant space. It modifies the existing linked list in place without creating any new data structures whose size depends on the input list size, N, where N is the number of nodes in the linked list. Therefore, the auxiliary space used remains constant, independent of the input size. The space complexity is O(1).

Edge Cases

Case	How to Handle
Empty linked list (head is null)	Return null immediately as there are no nodes to process.
Linked list with only one node and its value equals val	Return null since the only node needs to be removed.
Linked list with only one node and its value is not equal to val	Return the original list (head) as there is nothing to remove.
All nodes in the linked list have a value equal to val	Return null after removing all nodes.
The value 'val' appears at the beginning of the linked list	Update the head pointer to the first node whose value is not equal to val.
The value 'val' appears at the end of the linked list	Properly update the 'next' pointer of the node preceding the last node to null.
The value 'val' appears multiple times consecutively within the linked list	Traverse and skip all consecutive nodes with the value 'val'.
Very large linked list to test for performance and memory usage.	Iterative solution is preferred for space complexity; recursion might cause stack overflow.

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 linked list be empty (head is null)?
What is the range of values for nodes in the linked list and for the 'val' we need to remove?
If all nodes in the list have the value 'val', should I return null?
Are the node values integers?
Is it acceptable to modify the original linked list in place, or do I need to create a new one?

Brute Force Solution

Approach

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

Start at the beginning of the chain.
Look at the first item.
Is this the item you want to remove?
If yes, take it out of the chain. You might have to reconnect the items on either side of the removed item.
If no, move to the next item.
Repeat steps 2-5 for every item in the chain.

Code Implementation

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

def remove_linked_list_elements_brute_force(head, value):
    current_node = head
    previous_node = None

    while current_node:
        # Check if the current node's value matches the value to remove
        if current_node.val == value:
            if previous_node:
                # Bypass the current node to remove it
                previous_node.next = current_node.next

            else:
                # If the head node needs to be removed, update the head
                head = current_node.next

            current_node = current_node.next
        else:
            # Move both pointers forward
            previous_node = current_node
            current_node = current_node.next

    return head

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, imagine a 'helper' pointing right before the very start of your list. This makes it easier to change the beginning of the list if needed.
Move the 'helper' to the beginning of the real list.
Check if the very first item in the list should be removed. If it should, update the beginning of the list to skip over this unwanted item.
Now, go through the list one item at a time.
For each item, check if it should be removed.
If it should be removed, carefully 'unlink' it from the list. That means changing what the previous item points to, so it skips over the item being removed. The helper will not move.
If the current item should NOT be removed, simply move the 'helper' forward to the next item.
Keep going until you've checked every item in the list.
Finally, return the (potentially updated) beginning of the list.

Code Implementation

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

def removeElements(head: ListNode, value: int) -> ListNode:
    dummy_node = ListNode(0)
    dummy_node.next = head
    current_node = head
    previous_node = dummy_node

    # Use a helper to handle the head removal case elegantly.
    while current_node:
        if current_node.val == value:

            # Remove the node by updating the previous node's next pointer.
            previous_node.next = current_node.next
            current_node = current_node.next
        else:

            # Advance both pointers only if no removal is needed.
            previous_node = current_node
            current_node = current_node.next

    # The dummy node's next is now the new head.
    return dummy_node.next

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty linked list (head is null)	Return null immediately as there are no nodes to process.
Linked list with only one node and its value equals val	Return null since the only node needs to be removed.
Linked list with only one node and its value is not equal to val	Return the original list (head) as there is nothing to remove.
All nodes in the linked list have a value equal to val	Return null after removing all nodes.
The value 'val' appears at the beginning of the linked list	Update the head pointer to the first node whose value is not equal to val.
The value 'val' appears at the end of the linked list	Properly update the 'next' pointer of the node preceding the last node to null.
The value 'val' appears multiple times consecutively within the linked list	Traverse and skip all consecutive nodes with the value 'val'.
Very large linked list to test for performance and memory usage.	Iterative solution is preferred for space complexity; recursion might cause stack overflow.