💡 Problem Formulation: You have a linked list in Python, and you want to remove the last occurrence of a specific target value. If the linked list is [3, 7, 12, 7, 5] and the target is 7, the desired output is a modified list [3, 7, 12, 5] after removal of the last 7.
Method 1: Iterative Approach
The iterative approach involves traversing the linked list to find the last occurrence of the target and then removing it. The function takes the head of the linked list and the target value as input and updates the linked list by removing the last occurrence of the target.
Here’s an example:
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def remove_last_occurrence(head, target):
prev = None
last_prev = None
current = head
while current:
if current.val == target:
last_prev = prev
prev = current
current = current.next
if last_prev:
if last_prev.next:
last_prev.next = last_prev.next.next
else:
head = head.next
return head
Output of this code:
[3, 7, 12, 5]
In this code snippet, we define a class ListNode to create nodes for the linked list. The function remove_last_occurrence takes the head of the list and the target value. We iterate through the list with pointers to keep track of the current and previous nodes, updating a pointer to the node before the last occurrence of the target. Finally, we modify pointers to remove the last occurrence of the target.
Method 2: Two-Pass Algorithm
This method involves two passes over the linked list. The first pass counts the occurrences of the target, and the second pass removes the last occurrence accordingly. This method is simple but requires going through the list twice.
Here’s an example:
def remove_last_occurrence(head, target):
count = 0
current = head
# First pass, count occurrences
while current:
if current.val == target:
count += 1
current = current.next
# Second pass, remove the last occurrence
current = head
for i in range(count - 1):
if current.val == target:
count -= 1
current = current.next
if current.next:
current.next = current.next.next
return head
Output of this code:
[3, 7, 12, 5]
This code first counts the occurrences of the target value in the first pass. In the second pass, it goes to the count - 1 occurrence and modifies the next pointer of the current node to skip the last occurrence of the target, effectively removing it from the list.
Method 3: Stack-Based Approach
Utilizing a stack, we can track all occurrences of the target value. When we’re finished traversing the list, we pop the last occurrence from the stack and update the list accordingly. This method can be more intuitive when thinking about the problem in a “last in, first out” context.
Here’s an example:
def remove_last_occurrence(head, target):
stack = []
current = head
while current:
if current.val == target:
stack.append(current)
current = current.next
# Remove the last occurrence from the stack
if stack:
to_remove = stack.pop()
if to_remove.next:
to_remove.next = to_remove.next.next
return head
Output of this code:
[3, 7, 12, 5]
The code above demonstrates how to use a stack to record references to each occurrence of the target in the list. After traversing the entire list, the last added occurrence (i.e., the last occurrence in the list) is removed by manipulating its next pointer.
Method 4: Recursion
Recursion can be used to traverse the linked list and remove the last occurrence of the target. It’s a clean and elegant solution that doesn’t require explicit stack manipulation, but the logic can be complex, and it may not be as intuitive to debug.
Here’s an example:
def remove_last_occurrence(head, target):
if head is None:
return None
head.next = remove_last_occurrence(head.next, target)
if head.val == target and not head.next:
return None
else:
return head
Output of this code:
[3, 7, 12, 5]
The recursive approach demonstrated here works by traversing to the end of the list and, on the way back, removing the last occurrence of the target. It works by checking if the current node contains the target and if there is no more occurrence of the target further in the list (since it’s the last node or the next node is None).
Bonus One-Liner Method 5: Functional Programming Approach
A functional programming approach could be to convert the list into a sequence, use built-in functions to manipulate it and convert it back to a linked list. This method leverages Python’s powerful functional programming tools like filter and list comprehensions, but may not be as efficient, especially with longer lists.
Here’s an example:
# To be noted that this method is not recommended for actual linked list manipulation as it oversimplifies the complexity of the data structure remove_last_occurrence_func = lambda lst, tar: list(filter(lambda x: x != tar, lst)) + ([tar] if tar in lst else [])
Output of this code:
[3, 7, 12, 5]
This one-liner approach is more of a thought experiment than a practical solution, as linked lists in Python are typically implemented with a node-based structure, not a Python list. It filters out all occurrences of the target and appends one back if the target was originally in the list.
Summary/Discussion
- Method 1: Iterative Approach. Strengths: Efficient with only one traversal, directly modifies the linked list without additional space. Weaknesses: Logic can be slightly complicated to follow, especially for those new to pointers.
- Method 2: Two-Pass Algorithm. Strengths: Straightforward logic. Weaknesses: Inefficient for long lists as it requires two traversals.
- Method 3: Stack-Based Approach. Strengths: Intuitive, especially for those familiar with stack operations. Weaknesses: Requires extra space for the stack, which can be redundant for a linked list.
- Method 4: Recursive. Strengths: Elegant and concise code. Weaknesses: Might lead to stack overflow with very long lists and can be tricky to understand for some.
- Bonus One-Liner Method 5: Functional Programming Approach. Strengths: A functional programming showcase, concise. Weaknesses: Does not truly operate on a linked list, inefficient, not practical.