# Removing the Last Occurrence of an Element in a Linked List in Python

Rate this post

π‘ 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

prev = None
last_prev = None

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:

```

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
# First pass, count occurrences
while current:
if current.val == target:
count += 1
current = current.next

# Second pass, remove the last occurrence
for i in range(count - 1):
if current.val == target:
count -= 1
current = current.next
if current.next:
current.next = current.next.next
```

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 = []
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
```

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):
return None

return None
else:
```

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.