Remove Linked List Elements in O(n) Time Complexity using Python

Given the head of a singly 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:

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

Note:

Your algorithm should run in O(n) time and use O(1) extra space.

Understanding the Problem

The core challenge of this problem is to traverse the linked list and remove nodes that match a given value without using extra space. This is a common problem in linked list manipulation, often encountered in various applications such as data filtering and cleanup.

Potential pitfalls include handling the removal of nodes at the beginning (head) of the list and ensuring that the list remains connected after node removal.

Approach

To solve this problem, we can use a two-pointer technique. One pointer will traverse the list, and the other will help in removing the nodes. Here’s a step-by-step approach:

Naive Solution

A naive solution would involve creating a new linked list and copying over only the nodes that do not match the given value. However, this approach uses extra space, which violates the problem constraints.

Optimized Solution

We can optimize the solution by modifying the list in place. We will use a dummy node to handle edge cases where the head needs to be removed. The dummy node will point to the head of the list, and we will use a current pointer to traverse the list.

Algorithm

Here’s a step-by-step breakdown of the optimized algorithm:

Create a dummy node and set its next pointer to the head of the list.
Initialize a current pointer to the dummy node.
Traverse the list using the current pointer.
If the next node’s value matches the given value, adjust the next pointer to skip the node.
Otherwise, move the current pointer to the next node.
Return the next pointer of the dummy node as the new head of the list.

Code Implementation

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

def remove_elements(head: ListNode, val: int) -> ListNode:
    # Create a dummy node to handle edge cases
    dummy = ListNode(next=head)
    current = dummy
    
    while current.next:
        if current.next.val == val:
            # Skip the node with the given value
            current.next = current.next.next
        else:
            # Move to the next node
            current = current.next
    
    # Return the new head of the list
    return dummy.next

Complexity Analysis

The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list. This is because we traverse each node exactly once.

The space complexity is O(1) as we are not using any extra space that scales with the input size.

Edge Cases

Consider the following edge cases:

The list is empty (head is None).
All nodes in the list have the value to be removed.
No nodes in the list have the value to be removed.
The head node has the value to be removed.

Our algorithm handles these cases effectively by using a dummy node and adjusting pointers accordingly.

Testing

To test the solution comprehensively, consider the following test cases:

# Test case 1: Normal case
head = ListNode(1, ListNode(2, ListNode(6, ListNode(3, ListNode(4, ListNode(5, ListNode(6)))))))
val = 6
new_head = remove_elements(head, val)
# Expected output: [1, 2, 3, 4, 5]

# Test case 2: All nodes to be removed
head = ListNode(6, ListNode(6, ListNode(6)))
val = 6
new_head = remove_elements(head, val)
# Expected output: []

# Test case 3: No nodes to be removed
head = ListNode(1, ListNode(2, ListNode(3)))
val = 4
new_head = remove_elements(head, val)
# Expected output: [1, 2, 3]

# Test case 4: Empty list
head = None
val = 1
new_head = remove_elements(head, val)
# Expected output: []

Thinking and Problem-Solving Tips

When approaching linked list problems, always consider edge cases such as empty lists and single-node lists. Using a dummy node can simplify handling edge cases where the head needs to be removed.

Practice similar problems to improve your problem-solving skills. Understanding the underlying data structure and its operations is crucial for efficient solutions.

Conclusion

In this blog post, we discussed how to remove elements from a linked list in O(n) time complexity using Python. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is essential for mastering linked list manipulation and improving your coding skills.

Additional Resources

For further reading and practice, consider the following resources: