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

提示：

鏈表中結點的數目為 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

自解

(本來空間擊敗30，多提交兩次就96.74了，樂)

第一時間想到了反轉鏈表刪除對應節點后再反轉回去
考慮實用的話應該把刪去的節點空間回收

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 //反轉鏈表再反回去

struct ListNode* reverse_list(struct ListNode*head)//反轉鏈表
{
    struct ListNode *last=NULL,*next=NULL;
    while(head!=NULL)
    {
        next=head->next;
        head->next=last;
        last=head;
        head=next;
    }
    return last;
}



struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode *temp=NULL,*head1=NULL;
    head=reverse_list(head);//反轉
    head1=head;//記錄反轉后的頭節點
    if(n<=1)//如果刪除反轉后的首結點
    {
        head=reverse_list(head->next);//直接將頭節點之后節點反轉回去，返回反轉后的鏈表
        return head;
    }
    n--;//遍歷到刪除的節點前面那個
    while(--n)head=head->next;
    head->next=head->next->next;//去掉要刪掉的節點（實際要注意回收內存）
    head1=reverse_list(head1);//鏈表反轉后返回
    return head1;
    
}

力扣解

三個解答里我認為雙指針最優美
使用兩個指針，快指針比慢指針快n，當快指針到NULL時，慢指針就在第n個節點
當然這樣不太好直接刪除該節點，因此可以用一個dummy節點，讓慢指針再滯后一個節點，這樣快指針指向NULL時慢指針就是需要刪除節點的前一個結點。

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    dummy->val = 0, dummy->next = head;
    struct ListNode* first = head;
    struct ListNode* second = dummy;
    for (int i = 0; i < n; ++i) {
        first = first->next;
    }
    while (first) {
        first = first->next;
        second = second->next;
    }
    second->next = second->next->next;
    struct ListNode* ans = dummy->next;
    free(dummy);
    return ans;
}

作者：力扣官方題解
鏈接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/solutions/450350/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。