題目來源：Remove Nth Node From End of List

問題：
給予一個 Linked List, 試著刪除從尾巴算來第 N 個節點，並回傳 head

假設給予的 Linked List = 1->2->3->4->5, 並且 N = 2
再移除從尾巴算來第N個節點之後，這個 Linked List 會變成 1-->2->3->5

並且，題目給的 N 永遠都是有效的。
請嘗試在第一輪跑還就可以刪除並回傳結果。

想法：
這題目指定要從一個 Linked List 後面數來第 N 個節點，但又希望在第一輪（也就是每個節點只能訪問過一次）就要夠完成此任務。所以最簡單的方是就是另外宣告一個具有 index 的 ArrayList 來暫存，就可以在每個節點都訪問過一次後，直接針對該 index 去刪除。但如此一來的缺點就是要額外宣告記憶體空間使用才能完成。如果我們想要空間複雜度為 O(1) 的話，勢必不能這麼做。這時候我們可以利用多個指標來達成目的，就可以不用額外在宣告記憶體空間來暫存節點了。

如果要用指標來標記我們欲刪除的節點，我們就必須要知道指標應該要指在那邊，所以可以先考慮一下三個狀況：

1. 如果要刪除的節點是 第一個節點
2. 如果要刪除的節點是最 後一個節點
3. 如果要刪除的節點是 非頭也非尾 的節點

如果要刪除的節點是倒數最後一個節點，也就是第一個節點，那麼我們就必須要有一個假的節點來指向第一個節點。
dummyNode -> firstNode -> secondNode -> ... -> null
這時要刪除倒數最後一個節點的執行方是就是
dummyNode.next = firstNode.next
所以我們會需要有一個節點指向 firstNode, 而另一個節點指向 dummyNode。

如果我們要刪除的節點是倒數第一個節點，假設輸入的 Linked List 如下：
dummyNode -> firstNode -> secondNode -> ...(N-1)thNode -> NthNode -> null
這時要刪除倒數第一個節點的執行方式就是
(N-1)thNode.next = NthNode.next
所以我們同樣需要一個節點指向 (N-1)thNode , 另一個節點指向 NthNode。

不過問題來了，如果是倒數第一個節點，我可以利用 node.next == null，那如果是倒數最後一個節點呢？所以我們還需要一個節點來判斷是否已經到了最後一個節點了。

綜合以上判斷，我們需要的節點指標應該要有

1. deleteNode (指向要被刪除的節點)
2. dummyNode (指向 head 節點)
3. seekNode (最終要指向最後一個節點)
4. preDeleteNode (指向要被刪除的前一個節點)

那這三個指標節點的關係應該如何呢？以下用三張圖來觀察一下：

1. 假設 N = 5, 則這三個指標節的關係如下
   

2. 假設 N = 1, 則這三個指標節點關係如下
   

3. 假設 N = 3, 則這三個指標節點關係如下
   

從上面三張圖可以很清楚知道，preDeleteNode 一定會在 deleteNode 前面，seekNode 一定會指向最後一個節點。而 deleteNode 剛好是會指向倒數N個節點的位置。並且訪問節點的終止條件為 seekNode.next == null

java 主要的流程

while( seekNode.next != null ) {
    index += 1;
    seekNode = seekNode.next;
    if (index >= n)
        deleteNode = deleteNode.next;
    if (index >= n+1)
        preDeleteNode = preDeleteNode.next;
}

當 seekNode 訪問到最後一個節點時，這時候我們就可以把 deleteNode 給刪除了，並回傳 dummyNode 所指向的 LinkList 了。

preDeleteNode.next = deleteNode.next;
return dummyNode.next;

java 完整解答

public static ListNode remveFromEndNode(ListNode head, int n) {
    if (head == null)
        return null;
    
    ListNode dummyNode = new ListNode(0);
    dummyNode.next = head;
    
    ListNode deleteNode = dummyNode;
    ListNode preDeleteNode = dummyNode;
    ListNode seekNode = dummyNode;
    int index = 0;
        
    while(seekNode.next != null) {
        index += 1;
        
        seekNode = seekNode.next;
        if (index >= n)
            deleteNode = deleteNode.next;
        if (index >= n+1)
            preDeleteNode = preDeleteNode.next;
    }
        
    preDeleteNode.next = deleteNode.next;
    return dummyNode.next;
}

• 如果你用 Java or Python or C++ 可上 LeetCode Online Judge 驗證