題目
#

leetcode 19 - Remove Nth Node From End of List (題目說明請點連結)

題目簡述
#

給定一個鏈表，刪除倒數第 N 個節點，並返回鏈表的頭節點。

範例
#

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Explanation: 移除倒數第二個節點後，鏈表變為 [1,2,3,5]。

初始鏈表：

graph LR; A[1] --> B[2] --> C[3] --> D[4]:::remove --> E[5] classDef remove fill:#f96;

移除節點後的鏈表：

graph LR; A[1] --> B[2] --> C[3] --> E[5]

Example 2:

Input: head = [1], n = 1
Output: []
Explanation: 移除倒數第一個節點後，鏈表變為空。

初始鏈表：

graph LR; A[1]:::remove classDef remove fill:#f96;

移除節點後的鏈表：

graph LR; Empty[空]

Example 3:

Input: head = [1,2], n = 1
Output: [1]
Explanation: 移除倒數第一個節點後，鏈表變為 [1]。

初始鏈表：

graph LR; A[1] --> B[2]:::remove classDef remove fill:#f96;

移除節點後的鏈表：

graph LR; A[1]

解題思路
#

這題要求我們從一個單向鏈表中移除倒數第 N 個節點。我們可以使用雙指針的方法來解決這個問題，通過一個快指針和一個慢指針來找到需要移除的節點。

解法
#

用快慢指針

創建一個虛擬節點 dummy，指向鏈表的頭節點
初始化兩個指針 slow 和 fast，都指向 dummy
讓 fast 指針先移動 n+1 步
同時移動 slow 和 fast，直到 fast 到達鏈表的末尾
刪除 slow 指針的下一個節點
返回 dummy.next

步驟
#

初始化：
- 創建虛擬節點 dummy，初始化 slow 和 fast 指針
移動指針：
- 讓 fast 指針先移動 n+1 步
- 同時移動 slow 和 fast，直到 fast 到達鏈表的末尾
刪除節點：
- 刪除 slow 指針的下一個節點
返回結果：
- 返回 dummy.next

例子說明
#

head = [1,2,3,4,5], n = 2

步驟	slow	fast	操作
初始化	dummy	dummy	創建虛擬節點
移動 fast	dummy	3	fast 移動 n+1 步
移動 slow 和 fast	1	4	同時移動 slow 和 fast
移動 slow 和 fast	2	5	同時移動 slow 和 fast
刪除節點	3	null	刪除 slow 的下一個節點
最終結果	-	-	返回 [1,2,3,5]

初始鏈表：

graph LR; A[1] --> B[2] --> C[3] --> D[4]:::remove --> E[5] classDef remove fill:#f96;

移除節點後的鏈表：

graph LR; A[1] --> B[2] --> C[3] --> E[5]

完整程式碼
#

java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode();
        dummy.next = head;

        ListNode slow = dummy;
        ListNode fast = dummy;

        // 讓 fast 指針先移動 n+1 步
        for(int i = 0; i <= n; i++){
            fast = fast.next;
        }

        // 同時移動 slow 和 fast，直到 fast 到達鏈表的末尾
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }

        // 刪除 slow 的下一個節點
        slow.next = slow.next.next;

        // 返回新的頭節點
        return dummy.next;
    }
}