Remove Nth From End: khoảng cách cố định giữa hai pointer thay thế hoàn toàn việc đếm độ dài

Bài toán nghe có vẻ đơn giản — xóa node đứng cách đuôi n vị trí — nhưng có một ràng buộc làm nó thú vị: singly linked list chỉ cho phép đi về phía trước. Bạn không thể nhìn ngược. Điều đó có nghĩa là bạn không thể xuất phát từ cuối. Bạn phải tìm node cần xóa và node trước nó trong khi đang đi từ đầu, mà không biết trước độ dài danh sách.

Follow-up yêu cầu one pass. Đó không chỉ là thách thức bổ sung; đó là gợi ý rằng "có cách để không cần đếm trước." Hiểu tại sao one pass khả thi, và cơ chế gì tạo ra điều đó, mới là bài học thực sự của bài này.

Đề bài

Cho head của một singly linked list và số nguyên n, xóa node đứng cách đuôi danh sách n vị trí và trả về head. Full statement: LeetCode 19.

Ràng buộc:
- Số node trong danh sách là sz.
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz

Constraints nói gì

1 <= sz <= 30, 1 <= n <= sz. Hai điều rút ra ngay.

Thứ nhất, danh sách rất nhỏ. O(L) hoàn toàn ổn, thậm chí O(L²) cũng vượt qua được. Bài này không phải về đẩy độ phức tạp đến giới hạn — mà là về học một kỹ thuật. Constraints nói với bạn: hãy tập trung vào pointer mechanics, không phải tối ưu hóa vi mô.

Thứ hai, n được đảm bảo hợp lệ. Bạn không bao giờ phải xử lý n > sz. Node cần xóa luôn tồn tại. Điều đó đơn giản hóa code đáng kể: không cần kiểm tra biên cho n, không cần early return cho input không hợp lệ.

Về bản chất, bài toán "tìm node thứ n từ cuối" là bài toán chuyển đổi index. Nếu danh sách có độ dài L, node thứ n từ cuối nằm ở vị trí L - n từ đầu (0-indexed). Two-pass làm phép chuyển đổi đó tường minh. One-pass xây dựng phép chuyển đổi ẩn, thông qua khoảng cách không gian giữa hai pointer.

Approach 1: Two-pass — đếm trước, xóa sau

Cách đọc tự nhiên nhất: đi qua một lần để đo độ dài, tính vị trí mục tiêu từ đầu, đi qua lần thứ hai để đến đó.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        # Pass thứ nhất: đếm node
        length = 0
        current = head
        while current:
            length += 1
            current = current.next
 
        # Mục tiêu ở index (length - n) tính từ head, 0-indexed
        # Cần dừng ở index (length - n - 1): node predecessor
        target_pos = length - n
 
        # Trường hợp đặc biệt: xóa node head
        if target_pos == 0:
            return head.next
 
        # Pass thứ hai: đi đến predecessor
        current = head
        for _ in range(target_pos - 1):
            current = current.next
 
        # Nối bỏ qua node mục tiêu
        current.next = current.next.next
        return head

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}
 
public class Solution {
    public ListNode RemoveNthFromEnd(ListNode head, int n) {
        // Pass thứ nhất: đếm node
        int length = 0;
        ListNode current = head;
        while (current != null) {
            length++;
            current = current.next;
        }
 
        // Mục tiêu ở index (length - n) tính từ head
        int targetPos = length - n;
 
        // Trường hợp đặc biệt: xóa node head
        if (targetPos == 0) {
            return head.next;
        }
 
        // Pass thứ hai: đi đến predecessor
        current = head;
        for (int i = 0; i < targetPos - 1; i++) {
            current = current.next;
        }
 
        // Nối bỏ qua node mục tiêu
        current.next = current.next.next;
        return head;
    }
}

Thao tác xóa là current.next = current.next.next. Đó là cách xóa node tiêu chuẩn trong linked list: làm cho predecessor trỏ vượt qua node mục tiêu, ngắt kết nối nó khỏi chuỗi. Trong các ngôn ngữ garbage-collected, node bị ngắt kết nối sẽ được dọn dẹp tự động.

Trường hợp đặc biệt xóa head (target_pos == 0) là phần duy nhất hơi lộn xộn. Khi n == sz, node đầu tiên là mục tiêu, và predecessor không tồn tại. Bạn phải xử lý riêng vì không có gì để trỏ "vượt qua" head — bạn chỉ trả về head.next.

Time: O(L). Hai lần duyệt, mỗi lần tối đa L bước. Hằng số là 2, không liên quan đến asymptotic class.

Space: O(1). Một vài biến local; không có cấu trúc phụ trợ.

Approach 2: One-pass với two pointers và dummy node

Quan sát khéo léo: nếu bạn bắt đầu hai pointer tại cùng một vị trí và tiến một cái lên trước n+1 bước, chúng giờ cách nhau đúng n+1 node. Khi bạn tiến cả hai cùng nhau, khoảng cách đó được duy trì. Khi pointer trước chạm null (rơi khỏi cuối), pointer sau đang đứng đúng n vị trí trước đuôi — tức là một bước trước node cần xóa.

Tại sao n+1 chứ không phải n? Vì bạn cần predecessor, không phải bản thân node mục tiêu. Nếu fast cách slow n+1 bước và fast là null, slow.next là node mục tiêu. Cái "+1" đó là off-by-one quan trọng ở đây.

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
 
        fast = dummy
        slow = dummy
 
        # Tiến fast lên n+1 bước tính từ dummy
        for _ in range(n + 1):
            fast = fast.next
 
        # Di chuyển cả hai cho đến khi fast rơi khỏi cuối
        while fast:
            fast = fast.next
            slow = slow.next
 
        # slow giờ là predecessor của node mục tiêu
        slow.next = slow.next.next
 
        return dummy.next

public class Solution {
    public ListNode RemoveNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
 
        ListNode fast = dummy;
        ListNode slow = dummy;
 
        // Tiến fast lên n+1 bước tính từ dummy
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }
 
        // Di chuyển cả hai cho đến khi fast rơi khỏi cuối
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
 
        // slow giờ là predecessor của node mục tiêu
        slow.next = slow.next.next;
 
        return dummy.next;
    }
}

Hand trace: [1, 2, 3, 4, 5], n = 2

Đi qua từng bước di chuyển pointer.

Trạng thái ban đầu: dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
fast = dummy, slow = dummy

Tiến fast lên n+1 = 3 bước:
  bước 1: fast -> 1
  bước 2: fast -> 2
  bước 3: fast -> 3

Trạng thái sau khi tiến:
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
^slow               ^fast

Giờ di chuyển cả hai cùng nhau cho đến fast == null:
  lần 1: fast -> 4, slow -> 1
  lần 2: fast -> 5, slow -> 2
  lần 3: fast -> null, slow -> 3
  (vòng lặp kết thúc vì fast là null)

Trạng thái trước khi xóa:
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
                   ^slow       ^fast (null)

slow.next là node 4 (thứ 2 từ cuối). Xóa nó:
  slow.next = slow.next.next  ->  3.next = 5

Kết quả: dummy -> 1 -> 2 -> 3 -> 5 -> null
Trả về dummy.next = 1 (head ban đầu)

Khoảng cách được duy trì hoàn hảo xuyên suốt. Khi fast đến null, slow đứng sau ba vị trí — tại node 3, cách null đúng n+1 = 3 bước. Next của nó là node 4, node mục tiêu.

Time: O(L). Fast tiến tối đa L + 1 bước tổng cộng (n+1 trong setup, sau đó L - n trong joint walk). Slow tiến tối đa L - n bước. Mọi thứ đều tuyến tính theo L.

Space: O(1). Dummy node, fast, slow — ba pointer. Hằng số bất kể kích thước danh sách.

Tại sao dummy node không thể bỏ qua

Bỏ dummy node và thử xóa head (n = sz):

Không có dummy, n = sz = 5:
fast = head, tiến 5+1 = 6 bước
  bước 1: fast -> 2
  bước 2: fast -> 3
  bước 3: fast -> 4
  bước 4: fast -> 5
  bước 5: fast -> null
  bước 6: fast = null.next  -> NullPointerException

Dummy dịch chuyển cả hai pointer về một vị trí, nên fast tiến n+1 bước bắt đầu từ trước head thực sự. Khi n = sz, fast hạ cánh tại null sau đúng sz + 1 = L + 1 bước — không phải một bước vượt quá null. Không crash. Slow kết thúc tại dummy, và dummy.next = dummy.next.next thay thế head đúng cách.

Dummy node là trick cấu trúc thống nhất trường hợp xóa head với mọi trường hợp khác. Không có nó, bạn cần một if tường minh (như Approach 1) hoặc sẽ bị crash.

Các edge case thực sự cần suy nghĩ

Danh sách một node, n = 1: Node duy nhất vừa là head vừa là tail. Sau khi setup, fast tiến 2 bước từ dummy và hạ cánh tại null. Cả fast lẫn slow vẫn ở dummy (không có lần lặp joint walk nào). dummy.next = dummy.next.next = null. Trả về dummy.next = null. Đúng.

Xóa head của danh sách nhiều node (n = sz): Đã được phân tích trong phần dummy node ở trên. Slow kết thúc tại dummy, dummy.next = dummy.next.next bỏ qua head ban đầu. Hoạt động không cần trường hợp đặc biệt nào.

Xóa tail (n = 1): Fast tiến 2 bước từ dummy, đến node 2 (1-indexed). Rồi cả hai di chuyển về phía trước cùng nhau cho đến khi fast đến null sau node cuối cùng. Slow kết thúc ở node sz - 1. slow.next = slow.next.next = null, tách tail đúng cách.

Danh sách hai node: Hai trường hợp không tầm thường là n = 1 (xóa tail) và n = 2 (xóa head). Cả hai được xử lý bởi dummy node đồng nhất — không cần rẽ nhánh trong phiên bản one-pass.

Tất cả node có cùng giá trị: Không liên quan đến thuật toán. Việc xóa dựa trên vị trí, không dựa trên giá trị. Dummy node và pointer arithmetic không nhìn vào val chút nào.

Bảng so sánh

Cả hai đều O(L) time và O(1) space. Sự khác biệt là cấu trúc code, không phải độ phức tạp thuật toán.

Tôi sẽ ship cái nào và tại sao

Phiên bản two pointers, luôn luôn. Không phải vì nó là one pass — trên danh sách kích thước 30, hai lần duyệt so với một lần là tiếng ồn. Lý do thực sự là nó loại bỏ một nhánh if. Trường hợp xóa head là cùng một đoạn code với mọi trường hợp khác. Ít rẽ nhánh hơn có nghĩa là ít cần test hơn, ít cần maintain hơn, và ít cơ hội mắc off-by-one hơn.

Phiên bản two-pass hoàn toàn ổn để viết trước như một phác thảo — đó là cách đọc tự nhiên của bài toán. Sau đó refactor sang phiên bản one-pass để có cấu trúc sạch hơn, không rẽ nhánh.

Điều duy nhất bạn phải làm đúng trong phiên bản two pointers là kích thước gap. Là n+1, không phải n. Nếu bạn tiến fast chỉ n bước thay vì n+1, slow hạ cánh tại chính node mục tiêu, không phải predecessor của nó. Bạn có địa chỉ của node mục tiêu nhưng không có cách đến predecessor của nó trong singly linked list — việc xóa trở nên bất khả thi. Vẽ sơ đồ với ví dụ cụ thể mỗi lần bạn implement, cho đến khi "+1" trở thành tự động.

Pattern nền tảng và những bài tiếp theo

Kỹ thuật ở đây được gọi là fixed-gap two pointers: duy trì hai pointer với offset không đổi giữa chúng sao cho khi pointer dẫn đầu chạm biên, pointer theo sau đang đúng ở chỗ bạn cần. Đó là tương tự của sliding window trong linked list, chỉ khác là cửa sổ không bao giờ thu hẹp — bạn chỉ trượt nó về phía trước cùng nhau.

Cùng cấu trúc xuất hiện trong hầu hết các bài yêu cầu bạn tìm vị trí tương đối so với cuối danh sách mà không biết độ dài:

LeetCode 876 — Middle of the Linked List: Thay vì gap cố định, slow di chuyển một bước mỗi lần lặp và fast di chuyển hai bước. Khi fast đến cuối, slow đang ở giữa. Tỷ lệ tốc độ khác nhau, cùng ý tưởng — sử dụng mối quan hệ giữa hai vị trí pointer để suy ra một vị trí bạn không thể tra cứu trực tiếp.

LeetCode 141 — Linked List Cycle: Fast/slow pointers trở lại, nhưng giờ fast di chuyển nhanh gấp đôi. Nếu có cycle, fast đuổi kịp slow và chúng gặp nhau. Nếu không có cycle, fast rơi khỏi cuối. Boundary-hit so với meeting cho bạn câu trả lời.

LeetCode 61 — Rotate List: Xoay k vị trí tương đương với việc tìm tail mới — node thứ (sz - k % sz - 1) từ đầu. Đó là cùng bài toán "tìm node ở vị trí tương đối từ cuối" như LeetCode 19, chỉ được bọc trong thao tác rotation.

LeetCode 142 — Linked List Cycle II: Phát hiện điểm vào của cycle. Bước phát hiện là cách tiếp cận fast/slow tương tự như bài 141; tính toán entry point thêm một phase thứ hai. Khó hơn, nhưng cùng họ.

Bài này là bài thứ tư trong series linked-list ở đây, sau Reverse Linked List, Merge Two Sorted Lists, và Reorder List. Ba bài kia bao gồm pointer reversal mechanics và merge pattern. Remove Nth giới thiệu fixed-gap two-pointer idiom, sẽ xuất hiện lại trong các bài phát hiện cycle và rotation. Học được gap, và hầu hết các biến thể "tìm thứ n từ cuối" trở nên đơn giản.