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

def remove_elements(head, val):
    dummy_head = ListNode(0, head)
    current = dummy_head
    while current.next:
        if current.next.val == val:
            current.next = current.next.next
        else:
            current = current.next
    return dummy_head.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)
    sentinel.next = head
    prev, curr = sentinel, head
    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)
    sentinel.next = head
    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

def remove_elements(head, val):
    dummy_head = ListNode(0, head)
    current = dummy_head
    while current.next:
        if current.next.val == val:
            current.next = current.next.next
        else:
            current = current.next
    return dummy_head.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)
    sentinel.next = head
    prev, curr = sentinel, head
    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)
    sentinel.next = head
    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.