โปรแกรมลบการปรากฏครั้งสุดท้ายของ target ใน linked list ใน Python

สมมติว่ามี singly linked list และค่า target ต้องการลบโหนดที่มีค่า target ครั้งสุดท้าย

ตัวอย่าง: [5,4,2,6,5,2,3,2,4,5,4,7], target = 5 ผลลัพธ์ [5,4,2,6,5,2,3,2,4,4,7]

ขั้นตอนการแก้ปัญหา

1. head = node, k = None, prev = None, found = False
2. วนลูปผ่านลิสต์:
   • ถ้า node.val == target: found = True, prev = k
   • k = node, node = node.next
3. ถ้าไม่เจอ: คืน head
4. ถ้า prev is None (เจอที่หัว): คืน head.next
5. มิฉะนั้น: prev.next = prev.next.next, คืน head

ตัวอย่างโค้ด

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))

อินพุต

[5,4,2,6,5,2,3,2,4,5,4,7]

เอาต์พุต

[5, 4, 2, 6, 5, 2, 3, 2, 4, 4, 7, ]