題目：
?

給你一個鏈表，刪除鏈表的倒數第?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]

思路1：暴力遍歷

很簡單的遍歷完鏈表，一邊遍歷一邊計數n，刪除倒數第N個結點，即刪除正數第n-N+1個結點。

代碼實現：
?

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
int getlen(struct ListNode* head){int lenth=0;while(head){head=head->next;lenth++;}return lenth;
}
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {struct ListNode* dummy=malloc(sizeof(struct ListNode));dummy->val=0;dummy->next=head;struct ListNode* cur=dummy;int len=getlen(head);for(int i=0;i<len-n;i++){cur=cur->next;}cur->next=cur->next->next;struct ListNode* ans=dummy->next;free(dummy);return ans;
}

思路2：遞歸

鏈表天生自帶的遞歸性質在這個簡單條件面前自然也可以使用，在無法知道鏈表結點數的情況下，我們就自然無法在遞的上面做文章，自然而然就只能在歸的過程中進行計數，歸一次就計數N++

代碼實現：
?

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {static int N;//這里比較特別的一點就是我們使用靜態變量，作用是在不同的歸的棧中使得變量不改變while(!head){N=0;return head;}head->next=removeNthFromEnd(head->next, n);N++;if(N==n){struct ListNode* tmp=head->next;free(head);return tmp;}return head;
}

思路3：雙指針

第一個暴力遍歷的效率不高的一大原因就是因為遍歷的次數重復了一次，增添一個指針自然可以漸少一次遍歷，利用前后指針的范圍差，準確的確定倒數第N個結點的所在處

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {struct ListNode* dummy=malloc(sizeof(struct ListNode));dummy->val=0;dummy->next=head;struct ListNode* pre=dummy;struct ListNode* cur=dummy;for(int i=0;i<n-1;i++){cur=cur->next;}while(cur->next->next){pre=pre->next;cur=cur->next;}pre->next=pre->next->next;struct ListNode* tmp=dummy->next;free(dummy);return tmp;
}

思路4：棧

用棧來裝下所有的結點，再一步一步出棧。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct STACK{struct ListNode* val;struct STACK* next;};
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {struct ListNode* dummy=malloc(sizeof(struct ListNode));dummy->val=0;dummy->next=head;struct STACK* stk=NULL;struct ListNode* cur=dummy;while(cur){struct STACK* tmp=malloc(sizeof(struct STACK));tmp->val=cur;tmp->next=stk;stk=tmp;cur=cur->next;}for(int i=0;i<n;i++){struct STACK* tmp=stk->next;free(stk);stk=tmp;}struct ListNode* pre=stk->val;pre->next=pre->next->next;struct ListNode* ans=dummy->next;free(dummy);return ans;
}