โปรแกรมลบโหนด n ตัวหลังโหนด m ตัวใน Linked List ด้วย Python

ภาพรวม

ให้ Linked List เริ่มต้นที่ head และจำนวนเต็ม m, n ให้เก็บโหนดแรก m ตัว แล้วลบโหนดถัดไป n ตัว ทำซ้ำจนถึงท้ายลิสต์

ตัวอย่าง

อินพุต: [1,2,3,4,5,6,7,8], m=3, n=1

เก็บ 1,2,3 → ลบ 4 → เก็บ 5,6,7 → ลบ 8 → ผลลัพธ์: [1,2,3,5,6,7]

โครงสร้างโหนด

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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

1. ตั้งค่า prev = curr = head, q = 0
2. วนลูป while curr:
   • q += 1
   • ถ้า q == m:
     • วน n รอบ: ขยับ curr ไปข้างหน้า (ลบโหนด)
     • เชื่อม prev.next = curr.next
     • รีเซ็ต q = 0
   • prev = prev.next, curr = curr.next
3. คืนค่า head

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

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        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(']')

def solve(head, m, n):
    prev = curr = head
    q = 0
    while curr:
        q += 1
        if q == m:
            for _ in range(n):
                if curr.next is not None:
                    curr = curr.next
            prev.next = curr.next
            q = 0
        prev = prev.next
        curr = curr.next
    return head

head = make_list([1,2,3,4,5,6,7,8])
res = solve(head, 3, 1)
print_list(res)

อินพุต

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

เอาต์พุต

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