Technical Interview Question

You are given a singly linked list and a value val. Write a function to remove all instances of val from the linked list. The function should return the modified linked list.

Function Signature: def remove_elements(head: Optional[ListNode], val: int) -> Optional[ListNode]:

Input:

• head : the head node of a singly linked list (0 <= length <= $10^4$)
• val : an integer value representing the element to be removed from the linked list

Output:

• Return the head node of the modified linked list

Example

Input:

head = 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6, val = 6

Output:

head = 1 -> 2 -> 3 -> 4 -> 5

Explanation: In the given input, we need to remove all occurrences of the value 6 from the linked list. After removing all instances of 6, the modified linked list becomes 1 -> 2 -> 3 -> 4 -> 5.

Answer

To solve this problem, we can iterate through the linked list and remove any node with a value equal to val. We need to be careful with updating the pointers correctly to ensure that the modified linked list is formed properly.

Here is the step-by-step algorithm to solve this problem:

1. Initialize two pointers, prev and cur, and set them to the head of the linked list.
2. Iterate through the linked list using the current pointer cur.
3. If the value of the current node is equal to val, we need to remove it. To remove a node, we update the next pointer of the previous node to point to the node next to the current node. We can do this by setting prev.next = cur.next.
4. If the value of the current node is not equal to val, we move the prev pointer to the current node and update the cur pointer to the next node.
5. Repeat steps 3 and 4 until we reach the end of the linked list.
6. Finally, return the head of the modified linked list.

Here is the Python implementation of the above algorithm:

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

def remove_elements(head: Optional[ListNode], val: int) -> Optional[ListNode]:
    # Handle edge case of an empty linked list
    if not head:
        return None
    
    # Initialize prev and cur pointers
    prev = None
    cur = head
    
    # Iterate through the linked list
    while cur:
        # If the value of the current node is equal to val, remove it
        if cur.val == val:
            if prev:
                prev.next = cur.next
            else:
                head = cur.next
        else:
            prev = cur
        
        # Move the cur pointer to the next node
        cur = cur.next
    
    # Return the head of the modified linked list
    return head

The time complexity of this algorithm is O(n), where n is the length of the linked list. We need to iterate through the linked list once to remove the nodes with the given value. The space complexity is O(1) as we only need a few pointers to store the current and previous nodes.