給你一個鏈表，刪除鏈表的倒數第 n 個結點，並且返回鏈表的頭結點。

提示：

鏈表中結點的數目為 sz

• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

你能嘗試使用一趟掃描實現嗎？

具體實現

要刪除鏈表的倒數第 n 個節點，並返回鏈表的頭節點，我們可以使用一趟掃描的方法來實現。這個方法涉及使用兩個指針：快指針和慢指針。快指針先向前移動 n 步，然後慢指針從鏈表的頭節點開始，與快指針同時移動。當快指針到達鏈表的末尾時，慢指針所在的下一個節點就是倒數第 n 個節點。

以下是使用 Java 實現的刪除鏈表倒數第 n 個節點的函數：

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0); // 創建一個啞節點，它的下一個節點是頭節點
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;

        // 快指針先走 n 步
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        // 快慢指針同時移動，直到快指針指向鏈表的末尾
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 慢指針的下一個節點就是倒數第 n 個節點，刪除它
        slow.next = slow.next.next;

        return dummy.next; // 返回啞節點的下一個節點，即新的頭節點
    }
}

使用示例：

public class Main {
    public static void main(String[] args) {
        // 示例 1
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(3);
        head1.next.next.next = new ListNode(4);
        head1.next.next.next.next = new ListNode(5);
        int n1 = 2;
        ListNode newHead1 = new Solution().removeNthFromEnd(head1, n1);
        printList(newHead1); // 應該輸出 [1,2,3,5]

        // 示例 2
        ListNode head2 = new ListNode(1);
        int n2 = 1;
        ListNode newHead2 = new Solution().removeNthFromEnd(head2, n2);
        printList(newHead2); // 應該輸出 []

        // 示例 3
        ListNode head3 = new ListNode(1);
        head3.next = new ListNode(2);
        int n3 = 1;
        ListNode newHead3 = new Solution().removeNthFromEnd(head3, n3);
        printList(newHead3); // 應該輸出 [1]
    }

    private static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }
}

代碼輸出結果與題目中的示例輸出是一致， V 哥的這個實現中，使用了一個啞節點來簡化邊界條件的處理，這樣即使要刪除的是頭節點，代碼也能正常工作。這個方法只需要一趟掃描，因此時間複雜度是 O(sz)，其中 sz 是鏈表的長度。

實現過程和步驟如下

下面 V 哥把實現過程再詳細説明一下，為了幫助你更好的理解代碼的邏輯實現：

1. 創建一個啞節點（dummy node），並將其設置為鏈表的頭節點之前的一個節點。啞節點的引入是為了簡化邊界條件的處理，特別是當需要刪除的節點是頭節點時。
2. 初始化兩個指針：快指針（fast）和慢指針（slow），它們都指向啞節點。
3. 快指針先向前移動 n 步。這樣，快指針和慢指針之間就保持了 n 個節點的距離。
4. 快指針和慢指針同時向前移動，直到快指針到達鏈表的末尾（即快指針的下一個節點為 null）。此時，慢指針的位置就是倒數第 n 個節點的前一個節點。
5. 修改慢指針的 next 指針，使其指向下一個節點的下一個節點，從而跳過倒數第 n 個節點，實現刪除操作。
6. 返回啞節點的下一個節點，即新的頭節點。

這個方法的核心思想是利用快慢指針的差距來找到倒數第 n 個節點。快指針先走 n 步，然後快慢指針一起移動，直到快指針到達鏈表末尾。此時，慢指針所在的位置就是倒數第 n 個節點的前一個節點，這樣就可以很容易地刪除倒數第 n 個節點。

小結

V哥經過測試，坐實了這個方法只需要一趟掃描，所以時間複雜度是 O(sz)，其中 sz 是鏈表的長度。空間複雜度是 O(1)，因為只需要常數級別的額外空間來存儲快慢指針和啞節點。