1. 题目描述

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

2. 题目分析

典型的前后指针的题。

假如要求倒数第n个元素，先让ptrFirst指针以头元素为起点前进n+1步，然后让ptrSecond以头元素为起点，即此时ptrFirst比ptrSecond往前n+1步，ptrSecond和ptrFirst一起一格一格向前走，那么当ptrFirst第一次指向NULL的时候，ptrSecond指向的就是倒数第n+1个元素，那么此时删除倒数第n个元素也轻而易举了。

但如果将最初的head头节点作为头部元素其实会有漏洞，比如链表有三个元素，我现在要删除倒数第三个节点即头节点，那么按照上面的方法，ptrFirst得相对于头节点向前移动4步，而可以知道相对于head移动4步已经越界了，ptrFirst会指向NULL的next所以当然会报错。

所以为了处理这种特殊情况，继续搬出dummyHead这个大救星，让dummyHead的next指向head，而让ptrFirst和ptrSecond从dummyHead开始往后走，这样ptrFirst还是比ptrSecond往前n+1步，但很容易证明此时对于删除头节点这种特殊情况不会产生越界。

3. 代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode* dummyHead =
        (struct ListNode *)malloc(sizeof(struct ListNode));
    dummyHead->val = 0;
    dummyHead->next = head;
    struct ListNode* ptrFirst = dummyHead;
    struct ListNode* ptrSecond = dummyHead;
    
    for (int i = 0; i < n + 1; i++) {
        ptrFirst = ptrFirst->next;
    }

    while (ptrFirst) {
        ptrFirst = ptrFirst->next;
        ptrSecond = ptrSecond->next;
    }

    ptrSecond->next = ptrSecond->next->next;

    return dummyHead->next;
}

int main() {


    system("pause");
    return 0;
}