Remove Nth Node From End of List

Bài toán

Cho đầu 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ề head mới. Yêu cầu: Chỉ duyệt danh sách 1 lần (One pass).

Ví dụ:

Input: 1 -> 2 -> 3 -> 4 -> 5, n = 2
Output: 1 -> 2 -> 3 -> 5
Giải thích: Node thứ 2 từ cuối lên là 4. Xóa 4 đi.

Phân Tích & Tiếp Cận

Thách thức

Chúng ta không biết độ dài danh sách, nên không biết "thứ n từ cuối" là node nào nếu đi từ đầu. Cách ngây thơ: Duyệt lần 1 đếm độ dài L. Duyệt lần 2 tới vị trí L - n. -> 2 Pass (Không tối ưu).

Giải pháp: Two Pointers Gap (Khoảng cách)

Ta muốn khi con trỏ Right chạm đích (null), thì con trỏ Left đang đứng ngay trước node cần xóa. Để làm được điều này, Right phải đi trước Left đúng n + 1 bước (hoặc n bước tùy implementation).

Quy trình:

1. Dùng Dummy Node (để xử lý trường hợp xóa Head). Left trỏ dummy.
2. Cho Right chạy trước n bước (xuất phát từ head).
3. Sau đó di chuyển cả Left và Right cùng lúc cho đến khi Right chạm đích.
4. Lúc này, Left đang đứng trước node cần xóa. Thực hiện xóa: Left.next = Left.next.next.

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    const dummy = new ListNode(0);
    dummy.next = head;

    let left = dummy;
    let right = head;

    // 1. Cho Right chạy trước n bước
    while (n > 0 && right) {
        right = right.next;
        n--;
    }

    // 2. Di chuyển cả hai cho đến khi Right chạm đích
    while (right) {
        left = left.next!;
        right = right.next;
    }

    // 3. Xóa node
    // Lúc này left đang ở vị trí 'L-n-1' (ngay trước node cần xóa)
    left.next = left.next!.next;

    return dummy.next;
}

• Time Complexity: $O(n)$ - one pass.
• Space Complexity: $O(1)$.

Pattern Nhận Diện

Để tìm vị trí tương đối so với đích (ví dụ: thứ k từ dưới lên) mà không biết đích ở đâu, hãy dùng Two Pointers duy trì khoảng cách cố định. Con trỏ đi trước đóng vai trò như "thước đo" để dò tìm điểm kết thúc.