Use a dummy (sentinel) node that points to the head. Traverse the list with a pointer: if the next node's value matches val, skip it by updating the pointer; otherwise, advance. Return dummy.next as the new head.
Recursively process the list from the tail back. At each node, if its value matches val, return the result of the recursive call (skipping the node); otherwise, set head.next to the recursive result and return head.
""" 0203.1 - Solution 1 - Dummy Node Iteration """
#####################################################################################
# Imports
#####################################################################################
from typing import Optional
#####################################################################################
# Classes
#####################################################################################
class ListNode:
"""ListNode Class"""
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
"""Solution Class"""
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
"""Remove Linked List Elements Function"""
dummy = ListNode(0, head)
curr = dummy
while curr.next:
if curr.next.val == val:
curr.next = curr.next.next
else:
curr = curr.next
return dummy.next
#####################################################################################
# Functions
#####################################################################################
def build_list(values):
"""Helper to build a linked list from a list of values"""
dummy = ListNode(0)
curr = dummy
for v in values:
curr.next = ListNode(v)
curr = curr.next
return dummy.next
def to_list(head):
"""Helper to convert a linked list to a list"""
result = []
while head:
result.append(head.val)
head = head.next
return result
def testcase():
"""Test Function"""
s = Solution()
print(to_list(s.removeElements(build_list([1, 2, 6, 3, 4, 5, 6]), 6))) # [1, 2, 3, 4, 5]
print(to_list(s.removeElements(build_list([]), 1))) # []
print(to_list(s.removeElements(build_list([7, 7, 7, 7]), 7))) # []
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0203.2 - Solution 2 - Recursive Approach """
#####################################################################################
# Imports
#####################################################################################
from typing import Optional
#####################################################################################
# Classes
#####################################################################################
class ListNode:
"""ListNode Class"""
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
"""Solution Class"""
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
"""Remove Linked List Elements Function"""
if not head:
return None
head.next = self.removeElements(head.next, val)
return head.next if head.val == val else head
#####################################################################################
# Functions
#####################################################################################
def build_list(values):
"""Helper to build a linked list from a list of values"""
dummy = ListNode(0)
curr = dummy
for v in values:
curr.next = ListNode(v)
curr = curr.next
return dummy.next
def to_list(head):
"""Helper to convert a linked list to a list"""
result = []
while head:
result.append(head.val)
head = head.next
return result
def testcase():
"""Test Function"""
s = Solution()
print(to_list(s.removeElements(build_list([1, 2, 6, 3, 4, 5, 6]), 6))) # [1, 2, 3, 4, 5]
print(to_list(s.removeElements(build_list([]), 1))) # []
print(to_list(s.removeElements(build_list([7, 7, 7, 7]), 7))) # []
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()