Giả sử chúng ta có một danh sách được liên kết đơn lẻ và một giá trị khác được gọi là target, chúng ta phải xóa lần xuất hiện cuối cùng của target trong danh sách đã cho.
Vì vậy, nếu đầu vào là [5,4,2,6,5,2,3,2,4,5,4,7], target =5, thì đầu ra sẽ là [5, 4, 2, 6 , 5, 2, 3, 2, 4, 4, 7,]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- head:=node
- k:=null, trước:=null
- tìm thấy:=Sai
- trong khi nút không rỗng, hãy thực hiện
- nếu giá trị của nút giống với giá trị đích, thì
- tìm thấy:=True
- trước:=k
- k:=nút
- node:=next of node
- nếu giá trị của nút giống với giá trị đích, thì
- nếu tìm thấy là Sai, thì
- quay lại đầu
- nếu giá trị trước là null, thì
- quay lại phần tiếp theo của phần đầu
- nect of prev:=tiếp theo của kế tiếp của trước trước
- quay lại đầu
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class ListNode:
def __init__(self, data, next = None):
self.val = data
self.next = next
def make_list(elements):
head = ListNode(elements[0])
for element in elements[1:]:
ptr = head
while ptr.next:
ptr = ptr.next
ptr.next = ListNode(element)
return head
def print_list(head):
ptr = head
print('[', end = "")
while ptr:
print(ptr.val, end = ", ")
ptr = ptr.next
print(']')
class Solution:
def solve(self, node, target):
head = node
k = None
prev = None
found = False
while node:
if node.val == target:
found = True
prev = k
k = node
node = node.next
if found == False:
return head
if not prev:
return head.next
prev.next = prev.next.next
return head
ob = Solution()
L = make_list([5,4,2,6,5,2,3,2,4,5,4,7])
target = 5
print_list(ob.solve(L, target)) Đầu vào
[5,4,2,6,5,2,3,2,4,5,4,7]
Đầu ra
[5, 4, 2, 6, 5, 2, 3, 2, 4, 4, 7, ]