---

題目要求

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

題目示例

示例 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]

解題思路

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

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

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

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

條件轉(zhuǎn)換

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

核心思路

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

需要注意的點(diǎn)

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

改進(jìn)建議

• 創(chuàng)建一個(gè)前驅(qū)結(jié)點(diǎn)，快、慢指針都從前驅(qū)結(jié)點(diǎn)開始遍歷，這樣就可以成功的刪除頭結(jié)點(diǎn)并返回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é)果