Xóa nút thứ N từ cuối danh sách liên kết trong Python

Giả sử chúng ta có một danh sách liên kết. Chúng ta phải xóa nút thứ N từ cuối danh sách, sau đó trả về đầu danh sách. Ví dụ, nếu danh sách là [1, 2, 3, 4, 5, 6] và n = 3, danh sách trả về sẽ là [1, 2, 3, 5, 6].

Để giải quyết, chúng ta làm theo các bước sau:

• Nếu không có nút sau head, trả về None.
• front := head, back := head, counter := 0 và found := false.
• Khi counter <= n:
  • Nếu front không tồn tại, đặt flag thành true, thoát vòng lặp.
  • front := next của front, tăng counter lên 1.
• Khi front tồn tại:
  • front := next của front.
  • back := next của back.
• Nếu flag là false:
  • temp := next của back.
  • next của back := next của temp.
  • next của temp := None.
• Ngược lại head := next của head.
• Trả về head.

Ví dụ (Python)

Xem triển khai sau để hiểu rõ hơn:

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

Đầu vào

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

Đầu ra

[1,2,3,5,6]