---

題目要求

• 給你一個鏈表，刪除鏈表的倒數(shù)第n個結(jié)點，并且返回鏈表的頭結(jié)點。

題目示例

示例 1：

輸入：head = [1,2,3,4,5], n = 2
輸出：[1,2,3,5]

示例 2：
輸入：head = [1], n = 1
輸出：[]

示例 3：
輸入：head = [1,2], n = 1
輸出：[1]

解題思路

• 如果我們需要用一次掃描就完成這個操作，那么我們首先想到的一定是需要多個指針（結(jié)點）互相配合，才有可能一次掃描刪除指定結(jié)點的操作。
• 那么繼續(xù)思考，倒數(shù)第n個結(jié)點，輸入會給出n的值，那么我們需要考慮的是怎么根據(jù)給出的這個n值來定位到我們的目標(biāo)結(jié)點

從題目中的已知出發(fā)思考

尋找目標(biāo)結(jié)點

• 我們可以設(shè)想用兩個指針來尋找目標(biāo)結(jié)點，假設(shè)鏈表長度一共為lenth，倒數(shù)第n個就是正數(shù)第lenth-n+1個，那么也就是說需要一個指向頭結(jié)點的指針從頭結(jié)點開始走lenth-n步就走到了需要刪除的那個結(jié)點。

條件轉(zhuǎn)換

• 上述的尋找思路我們發(fā)現(xiàn)需要遍歷兩次鏈表才能實現(xiàn)，但是在要求遍歷一次時，我們就可以想到“快慢指針”（雙指針）

核心思路

• 定義一個快指針和一個慢指針都先指向頭結(jié)點，然后快指針先走n步，然后快、慢指針同時走，發(fā)現(xiàn)當(dāng)快指針走到鏈表結(jié)尾的時候，慢指針就剛好走到了要刪除結(jié)點的前一個結(jié)點，那么此時只需要將慢指針的next指向慢指針next的next即可完成刪除操作（就本題來說可以忽略釋放刪除結(jié)點這個操作，當(dāng)然釋放一下也可以）

需要注意的點

• 如果采用上面的思路操作的話，那么就會發(fā)現(xiàn)示例二是不能通過的，因為會出現(xiàn)野指針的問題。

改進(jìn)建議

• 創(chuàng)建一個前驅(qū)結(jié)點，快、慢指針都從前驅(qū)結(jié)點開始遍歷，這樣就可以成功的刪除頭結(jié)點并返回NULL了。

完整代碼

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* prehead = new ListNode(0);prehead->next = head;ListNode* slow = prehead;ListNode* fast = prehead;while(n--){fast = fast->next;}while(fast->next!=nullptr){fast = fast->next;slow = slow->next;}slow->next = slow->next->next;return prehead->next;}
};

提交結(jié)果