# 5 Best Ways to Remove All Nodes with Duplicate Values in a Python Linked List

Rate this post

π‘ Problem Formulation: In Python, managing data structures efficiently is crucial for performance-intensive applications. Removing nodes from a linked list with values matching a specific criterion is a common challenge. This article dives into various methods to eliminate nodes from a linked list when their value equals a predetermined one. For instance, given a linked list `1 -> 2 -> 3 -> 2 -> 4` and a value `2`, the desired output would be `1 -> 3 -> 4`.

## Method 1: Iterative Traversal

This method involves scanning the linked list node by node, using a while loop, and deleting nodes with matching values.

Here’s an example:

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

while current.next:
if current.next.val == val:
current.next = current.next.next
else:
current = current.next
```

Output:

`1 -> 3 -> 4`

This code snippet initializes a dummy head to simplify edge cases and iterates through the list. It checks each node and adjusts the `.next` pointer to skip over nodes with the target value, thereby removing them from the list.

## Method 2: Recursive Approach

Recursively navigate through the list, removing nodes with the target value by modifying the next pointer of previous nodes.

Here’s an example:

```def remove_elements_recursive(node, val):
if not node:
return None
node.next = remove_elements_recursive(node.next, val)
return node.next if node.val == val else node
```

Output:

`1 -> 3 -> 4`

The recursive method provides a concise and elegant way to remove nodes with the target value. It works by checking each node starting from the end of the list and adjusting the next pointers accordingly.

## Method 3: Two-pointer Technique

Implement a two-pointer technique where one pointer tracks the current node while the other tracks the last distinct node encountered.

Here’s an example:

```def remove_elements_two_pointers(head, val):
sentinel = ListNode(0)
while curr:
if curr.val == val:
prev.next = curr.next
else:
prev = curr
curr = curr.next
return sentinel.next
```

Output:

`1 -> 3 -> 4`

The two-pointer method increases clarity and efficiency in instances where space complexity is a concern. It eliminates the need for a dummy node by maintaining a reference to the last unremoved node.

## Method 4: Using a Sentinel Node

The sentinel node method simplifies the process of node removal by providing a dummy head that leads the original list, making edge case management easier.

Here’s an example:

```def remove_elements_sentinel(head, val):
sentinel = ListNode(0)
prev, curr = sentinel, sentinel.next
while curr:
if curr.val == val:
prev.next = curr.next
else:
prev = curr
curr = curr.next
return sentinel.next
```

Output:

`1 -> 3 -> 4`

Using a sentinel node eliminates the hassle of handling special conditions like removal of the first element. It streamlines the removal process across the linked list.

## Bonus One-Liner Method 5: List Comprehension with Recursion

Combine the power of list comprehension and recursion to create a one-liner that removes all nodes with the specified value.

Here’s an example:

```remove_elements = lambda node, val: node and (node.next, node)[node.val != val] and remove_elements(node.next, val) or node
```

Output:

`1 -> 3 -> 4`

This intriguing one-liner utilizes Python’s lambda functions and ternary conditional operator to compactly express the removal process. It is an advanced method that obfuscates readability for brevity.

## Summary/Discussion

• Method 1: Iterative Traversal. This method is straightforward and easy to understand. It works well for most use cases but may not be as elegant as recursive solutions.
• Method 2: Recursive Approach. Recursive implementations are elegant and can lead to cleaner code. However, they might lead to a stack overflow for very long lists.
• Method 3: Two-pointer Technique. This method can be more intuitive for individuals comfortable with pointers and reduces extra space used by dummy nodes.
• Method 4: Using a Sentinel Node. This approach simplifies edge cases but does practically the same as the two-pointer technique and could be considered redundant.
• Bonus One-Liner Method 5: A compact and clever solution for fans of functional programming, though it may compromise on readability and could be inefficient due to the absence of short-circuiting in the recursion.

This method involves scanning the linked list node by node, using a while loop, and deleting nodes with matching values.

Here’s an example:

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

while current.next:
if current.next.val == val:
current.next = current.next.next
else:
current = current.next
```

Output:

`1 -> 3 -> 4`

This code snippet initializes a dummy head to simplify edge cases and iterates through the list. It checks each node and adjusts the `.next` pointer to skip over nodes with the target value, thereby removing them from the list.

## Method 2: Recursive Approach

Recursively navigate through the list, removing nodes with the target value by modifying the next pointer of previous nodes.

Here’s an example:

```def remove_elements_recursive(node, val):
if not node:
return None
node.next = remove_elements_recursive(node.next, val)
return node.next if node.val == val else node
```

Output:

`1 -> 3 -> 4`

The recursive method provides a concise and elegant way to remove nodes with the target value. It works by checking each node starting from the end of the list and adjusting the next pointers accordingly.

## Method 3: Two-pointer Technique

Implement a two-pointer technique where one pointer tracks the current node while the other tracks the last distinct node encountered.

Here’s an example:

```def remove_elements_two_pointers(head, val):
sentinel = ListNode(0)
while curr:
if curr.val == val:
prev.next = curr.next
else:
prev = curr
curr = curr.next
return sentinel.next
```

Output:

`1 -> 3 -> 4`

The two-pointer method increases clarity and efficiency in instances where space complexity is a concern. It eliminates the need for a dummy node by maintaining a reference to the last unremoved node.

## Method 4: Using a Sentinel Node

The sentinel node method simplifies the process of node removal by providing a dummy head that leads the original list, making edge case management easier.

Here’s an example:

```def remove_elements_sentinel(head, val):
sentinel = ListNode(0)
prev, curr = sentinel, sentinel.next
while curr:
if curr.val == val:
prev.next = curr.next
else:
prev = curr
curr = curr.next
return sentinel.next
```

Output:

`1 -> 3 -> 4`

Using a sentinel node eliminates the hassle of handling special conditions like removal of the first element. It streamlines the removal process across the linked list.

## Bonus One-Liner Method 5: List Comprehension with Recursion

Combine the power of list comprehension and recursion to create a one-liner that removes all nodes with the specified value.

Here’s an example:

```remove_elements = lambda node, val: node and (node.next, node)[node.val != val] and remove_elements(node.next, val) or node
```

Output:

`1 -> 3 -> 4`

This intriguing one-liner utilizes Python’s lambda functions and ternary conditional operator to compactly express the removal process. It is an advanced method that obfuscates readability for brevity.

## Summary/Discussion

• Method 1: Iterative Traversal. This method is straightforward and easy to understand. It works well for most use cases but may not be as elegant as recursive solutions.
• Method 2: Recursive Approach. Recursive implementations are elegant and can lead to cleaner code. However, they might lead to a stack overflow for very long lists.
• Method 3: Two-pointer Technique. This method can be more intuitive for individuals comfortable with pointers and reduces extra space used by dummy nodes.
• Method 4: Using a Sentinel Node. This approach simplifies edge cases but does practically the same as the two-pointer technique and could be considered redundant.
• Bonus One-Liner Method 5: A compact and clever solution for fans of functional programming, though it may compromise on readability and could be inefficient due to the absence of short-circuiting in the recursion.