Remove Nth Node From End of List ใน Python - ลบโหนดที่ N จากท้าย

สมมติว่าเรามี linked list เราต้องลบโหนดที่ N จากท้ายของลิสต์ แล้วคืน head ตัวอย่าง ลิสต์ [1,2,3,4,5,6] และ n = 3 ลิสต์ที่คืนคือ [1,2,3,5,6]

ขั้นตอนการทำงาน (Two Pointers / Fast-Slow Pointer)

1. ถ้าไม่มีโหนดหลัง head ให้คืน None
2. front := head, back := head, counter := 0, flag := false
3. วนลูป while counter <= n:
   • ถ้า front ไม่มี: ตั้ง flag true, ออกจากลูป
   • front := next of front, เพิ่ม counter
4. วนลูป while front exists:
   • front := next of front
   • back := next of back
5. ถ้า flag false:
   • temp := next of back
   • next of back := next of temp
   • next of temp := None
6. มิฉะนั้น head := next of head
7. คืน head

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

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(object):
    def removeNthFromEnd(self, head, n):
        if not head.next:
            return None
        front = head
        back = head
        counter = 0
        flag = False
        while counter <= n:
            if not front:
                flag = True
                break
            front = front.next
            counter += 1
        while front:
            front = front.next
            back = back.next
        if not flag:
            temp = back.next
            back.next = temp.next
            temp.next = None
        else:
            head = head.next
        return head

head = make_list([1,2,3,4,5,6])
ob1 = Solution()
print_list(ob1.removeNthFromEnd(head, 3))

อินพุต

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

เอาต์พุต

[1,2,3,5,6]