Cho một danh sách liên kết đơn và một số nguyên n, yêu cầu là xóa node thứ n tính từ cuối danh sách và trả về con trỏ đầu tiên của danh sách sau khi đã xóa.

Ví dụ minh họa

• Ví dụ 1:

  [1, 2, 3, 4, 5], n = 2 → Kết quả: [1, 2, 3, 5]

• Ví dụ 2:

  [1], n = 1 → Kết quả: []

• Ví dụ 3:

  [1, 2], n = 1 → Kết quả: [1]

Phương pháp giải quyết

Điểm khó ở bài toán này là không thể truy cập ngẫu nhiên như mảng để tìm vị trí phần tử thứ n từ cuối. Giải pháp hiệu quả sử dụng hai con trỏ (fast-slow pointer).

Cách tiếp cận chính:

1. Di chuyển con trỏ nhanh trước n bước.
2. Sau đó cả hai con trỏ cùng di chuyển song song cho đến khi con trỏ nhanh đến cuối danh sách.
3. Khi đó, con trỏ chậm sẽ nằm đúng tại vị trí phía trước node cần xóa.

Để xử lý trường hợp đặc biệt khi node cần xóa là node đầu tiên, ta thêm vào một node giả gọi là sentinel hoặc dummy node.

Mã nguồn Python

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

def delete_nth_from_end(head: ListNode, n: int) -> ListNode:
    sentinel = ListNode(0)
    sentinel.next = head
    
    ahead = sentinel
    behind = sentinel

    # Di chuyển ahead đi n bước
    for _ in range(n):
        ahead = ahead.next

    # Cả hai cùng tiến tới khi ahead đến cuối
    while ahead.next:
        ahead = ahead.next
        behind = behind.next

    # Xóa node tiếp theo của behind
    behind.next = behind.next.next

    return sentinel.next

Giải thích từng bước

Bước 1: Tạo node giả

sentinel = ListNode(0)
sentinel.next = head

Node sentinel giúp xử lý thống nhất mọi trường hợp, kể cả khi node bị xóa là node đầu tiên.

Bước 2: Khởi tạo hai con trỏ

ahead = sentinel
behind = sentinel

Bước 3: ahead di chuyển trước n bước

for _ in range(n):
    ahead = ahead.next

Bước 4: Cùng di chuyển đến cuối

while ahead.next:
    ahead = ahead.next
    behind = behind.next

Bước 5: Thực hiện thao tác xóa

behind.next = behind.next.next

Bước 6: Trả về danh sách mới

return sentinel.next

Minh họa bằng tay

Dữ liệu đầu vào: [1, 2, 3, 4, 5], n = 2.

1. Khởi tạo với sentinel:

   sentinel -> 1 -> 2 -> 3 -> 4 -> 5 -> null

2. Ahead đi 2 bước:
   • Bước 1: ahead → 1
   • Bước 2: ahead → 2
3. Cả hai cùng tiến:
   • Bước 3: ahead → 3, behind → 1
   • Bước 4: ahead → 4, behind → 2
   • Bước 5: ahead → 5, behind → 3
4. Lúc này behind trỏ đến node có giá trị 3. Ta thực hiện:

   behind.next = behind.next.next

   Kết quả:

   sentinel -> 1 -> 2 -> 3 -> 5 -> null

Phân tích độ phức tạp

• Thời gian: O(L), với L là độ dài danh sách – chỉ duyệt qua danh sách một lần.
• Bộ nhớ: O(1) – chỉ dùng vài biến phụ trợ.

Tổng kết

Bài toán được giải quyết bằng kỹ thuật hai con trỏ rất phổ biến trong cấu trúc dữ liệu danh sách liên kết:

• Sử dụng sentinel giúp đơn giản hóa logic và tránh kiểm tra riêng lẻ cho các trường hợp biên.
• Con trỏ ahead tạo ra khoảng cách cố định n so với behind.
• Khi ahead đến cuối thì behind dừng đúng trước node mục tiêu.

Đây là mẫu hình thường gặp trong nhiều bài toán khác như tìm phần tử giữa danh sách, xoay vòng danh sách,... Việc nắm vững cơ chế hoạt động của hai con trỏ giúp mở rộng tư duy thuật toán trên cấu trúc tuyến tính.