Leetcode – Remove Linked List Elements Solution in Python

The Remove Linked List Elements problem on LeetCode is a classic example that tests your knowledge and skill in manipulating linked list data structures. This problem is especially good for beginners to get comfortable with traversing linked lists and modifying links between nodes. In this article, we will explore the problem statement in depth, discuss various strategies for solving the problem, and implement these solutions in Python.

Problem Statement

The Remove Linked List Elements problem is listed as problem number 203 on LeetCode. Here’s the problem statement:

Remove all elements from a linked list of integers that have a value equal to val.

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: []

Understanding the Problem

The task is straightforward: You are given the head of a singly linked list and an integer val. You need to remove all the nodes that have the value val and return the modified head of the linked list.

Approach 1: Basic Traversal and Modification

One simple approach is to traverse the linked list and unlink all the nodes with the value equal to val.

To start, you’ll have to handle a special case separately: if the head itself needs to be deleted. Since the head is the only reference to the list, you must change it to the next node in this case.

For other cases, while you traverse the list, keep track of the previous node. If you find a node that should be deleted, modify the next pointer of the previous node.

Here’s the code in Python:

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

def removeElements(head, val):
    # Handling the special case
    while head and head.val == val:
        head = head.next
        
    # Traverse the list and unlink nodes
    current = head
    while current and current.next:
        if current.next.val == val:
            current.next = current.next.next
        else:
            current = current.next
            
    return head

This approach has a time complexity of O(n) and a space complexity of O(1).

Approach 2: Sentinel Node

The special case of the head node can be handled more elegantly by introducing a sentinel node. A sentinel node is an auxiliary node, typically used to simplify edge cases. In this scenario, we can add a sentinel node in front of the head node. This way, we don’t have to handle the head node separately.

Here’s the updated code:

def removeElements(head, val):
    # Add sentinel node
    sentinel = ListNode(0)
    sentinel.next = head
    current = sentinel
    
    # Traverse the list and unlink nodes
    while current.next:
        if current.next.val == val:
            current.next = current.next.next
        else:
            current = current.next
            
    return sentinel.next

This approach also has a time complexity of O(n) and a space complexity of O(1), but it’s cleaner and avoids the special case handling.

Conclusion

The Remove Linked List Elements problem is a quintessential linked list manipulation problem that emphasizes the importance of careful traversal and pointer adjustment. Through the different approaches discussed, we understand the value of handling edge cases gracefully and the utility of sentinel nodes in simplifying code. Being adept at linked list manipulation is an essential skill for any programmer, as the principles of linked lists are widely applicable in software development.