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 nodeExample 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | # 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 |
# 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) —
GD Star Rating
loading...
250 wordsloading...
Last Post: Teaching Kids Programming - Revisit the Symmetric Binary Tree by Using Clone and Invert Algorithm
Next Post: Teaching Kids Programming - Recursive Algorithm to Convert a Sorted List to a Balanced Binary Search Tree
Jon stole your code. Just so you know.