Linked List Delete Last Occurrence of Value

Given a singly linked list node, and an integer target, delete the last occurrence of target in node.

Constraints
0 ≤ n ≤ 100,000 where n is the number of nodes in node

Example 1
Input
Visualize
node = [1, 2, 3, 1]
target = 1
Output
Visualize
[1, 2, 3]

Example 2
Input
Visualize
node = [1, 2, 3, 1]
target = 3
Output
Visualize
[1, 2, 1]

Algorithm to Delete the Last Occurence Node

We need to search in O(N) time for the last occurence in the Link List and record the node and its previous node. In order to deal with the first (head) node more naturally, we use a dummy head which points to the first node so all cases can be handled.

# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeLastOccurrence(self, node, target):
        dummy = LLNode(-1)
        dummy.next = node
        last, lastPrev = None, None
        prev = dummy
        while node:
            if node.val == target:
                lastPrev = prev
                last = node
            prev = node
            node = node.next
        if lastPrev:
            lastPrev.next = last.next
        return dummy.next

–EOF (The Ultimate Computing & Technology Blog) —