Algos 101: Bài 4, Hướng dẫn chi tiết cách giải bài Remove Nth Node From End of List bằng Python

Chào các bạn! Trong quá trình chuẩn bị cho các buổi phỏng vấn kỹ thuật tại các công ty công nghệ lớn, các bài toán liên quan đến Danh Sách Liên Kết (Linked List) luôn là một chủ đề cực kỳ quen thuộc. Một trong những bài toán kinh điển nhất chính là Remove Nth Node From End of List (Xóa node thứ N tính từ cuối danh sách).

Hôm nay, chúng ta sẽ cùng nhau đi từ ý tưởng thô sơ đến giải pháp tối ưu chỉ với một lần duyệt duy nhất bằng kỹ thuật hai con trỏ (Fast & Slow Pointers).

---

📌 Phân Tích Đề Bài

Đề bài yêu cầu: Cho đầu (head) của một danh sách liên kết, hãy xóa node thứ n tính từ cuối danh sách và trả về đầu danh sách sau khi đã chỉnh sửa.

• Input: head = [1, 2, 3, 4, 5], n = 2
• Output: [1, 2, 3, 5]
• Giải thích: Node thứ 2 tính từ cuối là node có giá trị 4. Sau khi xóa node này, danh sách còn lại là [1, 2, 3, 5].

Các Ràng Buộc (Constraints):

• Số lượng node trong danh sách là sz và \(1 \le sz \le 30\).
• Giá trị mỗi node: \(0 \le Node.val \le 100\).
• Vị trí cần xóa: \(1 \le n \le sz\).
• Thách thức: Giải bài toán in-place (không dùng thêm bộ nhớ phụ trợ) với độ phức tạp thời gian là $O(N)$ và chỉ duyệt qua danh sách đúng một lần (single pass).

---

💡 Ý Tưởng Thuật Toán

1. Cách Tiếp Cận Duyệt Hai Lần (Brute-Force)

Ý tưởng đơn giản nhất xuất hiện ngay trong đầu chúng ta là:

1. Duyệt qua toàn bộ danh sách để đếm tổng số node (gọi là L).
2. Node thứ n từ cuối thực chất là node thứ L - n + 1 từ đầu.
3. Duyệt lại lần thứ hai đến node thứ L - n (node ngay trước node cần xóa), cập nhật con trỏ next của nó bỏ qua node thứ L - n + 1.

• Độ phức tạp:
  • Thời gian: $O(N)$ (nhưng phải duyệt danh sách 2 lần).
  • Không gian: $O(1)$.

Câu hỏi đặt ra từ người phỏng vấn: "Làm thế nào để giải quyết bài toán này chỉ với duy nhất một lần duyệt?"

---

2. Giải Pháp Tối Ưu: Kỹ Thuật Hai Con Trỏ (Fast & Slow Pointers)

Để tìm được node thứ n từ cuối chỉ trong 1 lần duyệt, chúng ta có thể tạo ra một khoảng cách cố định bằng n giữa hai con trỏ:

• Đặt một con trỏ fast đi trước. Cho nó đi trước n bước.
• Sau đó, cho cả hai con trỏ fast và slow cùng di chuyển với tốc độ như nhau (mỗi lượt 1 bước).
• Khi con trỏ fast chạm đến cuối danh sách (giá trị None), con trỏ slow sẽ dừng lại ngay tại vị trí node ngay trước node cần xóa.

Sử Dụng Node Giả (Dummy Node)

Một kỹ thuật cực kỳ quan trọng khi xử lý Linked List là sử dụng một Dummy Node. dummy node trỏ đến head giúp chúng ta:

• Tránh việc phải xử lý trường hợp đặc biệt khi node cần xóa chính là node đầu tiên (head).
• Giữ tham chiếu đến đầu danh sách mới một cách dễ dàng thông qua dummy.next.

---

📊 Minh Họa Từng Bước Chạy (State Walkthrough)

Hãy cùng chạy thử ví dụ với head = [1, 2, 3, 4, 5] và n = 2.

1. Khởi tạo: Tạo dummy trỏ đến head. Đặt fast và slow ở dummy.

   [dummy] -> [1] -> [2] -> [3] -> [4] -> [5] -> None
      ^
   fast, slow
   

2. Cho fast đi trước n + 1 bước (ở đây là 3 bước):

   • Bước 1: fast trỏ tới 1
   • Bước 2: fast trỏ tới 2
   • Bước 3: fast trỏ tới 3

   [dummy] -> [1] -> [2] -> [3] -> [4] -> [5] -> None
      ^                        ^
     slow                     fast
   

3. Di chuyển cả fast và slow cùng lúc cho đến khi fast là None:

   • Lần dịch 1:

     [dummy] -> [1] -> [2] -> [3] -> [4] -> [5] -> None
                 ^                        ^
               slow                      fast
     

   • Lần dịch 2:

     [dummy] -> [1] -> [2] -> [3] -> [4] -> [5] -> None
                         ^                        ^
                       slow                      fast
     

   • Lần dịch 3:

     [dummy] -> [1] -> [2] -> [3] -> [4] -> [5] -> None
                                 ^                 ^
                               slow               fast
     

     Lúc này fast đã trở thành None. Dừng vòng lặp.

4. Xóa node: slow.next hiện tại trỏ đến 4. Ta thực hiện slow.next = slow.next.next (bỏ qua 4 và trỏ thẳng tới 5).

   [dummy] -> [1] -> [2] -> [3] ------> [5] -> None
                                   ^
                                 slow
   

Trả về dummy.next chính là [1, 2, 3, 5].

---

💻 Cài Đặt Python (Python Implementation)

Dưới đây là mã nguồn Python hoàn chỉnh được triển khai tối ưu:

from typing import Optional

class ListNode:
    def __init__(self, val: int = 0, next: Optional['ListNode'] = None):
        self.val = val
        self.next = next

def remove_nth_from_end(head: Optional[ListNode], n: int) -> Optional[ListNode]:
    if not head:
        return None
    
    # Tạo dummy node trỏ đến head để xử lý trường hợp xóa node đầu tiên dễ dàng
    dummy = ListNode(0, head)
    fast = dummy
    
    # 1. Cho con trỏ fast đi trước n + 1 bước
    for i in range(n + 1):
        if fast is None:
            return head
        fast = fast.next
        
    slow = dummy
    
    # 2. Di chuyển cả hai con trỏ cùng lúc
    while fast:
        fast = fast.next
        slow = slow.next
        
    # 3. slow hiện tại ở ngay trước node cần xóa. Thực hiện xóa node.
    if slow and slow.next:
        slow.next = slow.next.next
        
    # Trả về head thực sự của danh sách đã cập nhật
    return dummy.next

---

📈 Phân Tích Độ Phức Tạp

• Thời gian (Time Complexity): $O(N)$ với $N$ là số lượng node trong danh sách. Chúng ta chỉ duyệt qua danh sách đúng một lần duy nhất bằng con trỏ fast.
• Không gian (Space Complexity): $O(1)$ auxiliary space. Chúng ta chỉ sử dụng một vài con trỏ bổ sung (fast, slow, dummy) và thay đổi liên kết trực tiếp trên các node có sẵn.

---

💡 Trường Hợp Biên & Lưu Ý Khi Phỏng Vấn

Khi phỏng vấn về danh sách liên kết, các kỹ sư phỏng vấn rất chú trọng đến cách bạn xử lý các góc cạnh (edge cases):

1. Xóa node đầu tiên (Head): Khi \(n = sz\), node cần xóa chính là head. Nhờ có dummy node nằm ở trước head, slow sẽ đứng ở dummy và slow.next = slow.next.next sẽ tự động cập nhật head mới một cách trơn tru.
2. Danh sách chỉ có 1 phần tử: Ví dụ head = [1], n = 1. dummy trỏ tới 1. fast dịch 2 bước thành None. slow vẫn ở dummy. Thực hiện xóa node 1, trả về None. Code hoạt động hoàn hảo.
3. Hỏi về Garbage Collection: Trong Python, khi ta ngắt liên kết slow.next = slow.next.next, node bị ngắt kết nối sẽ không còn được tham chiếu và sẽ được dọn dẹp tự động bởi bộ dọn rác (Garbage Collector). Tuy nhiên, trong C/C++, bạn cần phải giải phóng vùng nhớ (free/delete) của node bị xóa để tránh rò rỉ bộ nhớ (memory leak).

---

🏁 Kết Luận

Kỹ thuật khoảng cách cố định (sliding window/two pointers) áp dụng trên Linked List cực kỳ hiệu quả để giải quyết các bài toán liên quan đến vị trí tương đối từ cuối lên mà không cần biết trước chiều dài danh sách.

Chúc các bạn luyện tập tốt và chinh phục thành công các buổi phỏng vấn DSA sắp tới! Đừng ngần ngại để lại bình luận nếu có bất kỳ thắc mắc nào nhé! 😉