描述

给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针
例如，
给出的链表为: 1\to 2\to 3\to 4\to 51→2→3→4→5, n= 2n=2.
删除了链表的倒数第 nn 个节点之后,链表变为1\to 2\to 3\to 51→2→3→5.

数据范围： 链表长度 0\le n \le 10000≤n≤1000，链表中任意节点的值满足 0 \le val \le 1000≤val≤100
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
备注：
题目保证 nn 一定是有效的

示例1

输入： 
{1,2},2
复制
返回值： 
{2}
解题思路：
1、本题主要使用快慢指针的思想，因为无法逆序遍历链表，所以可以使用快慢指针，快指针先走N步，这样当快指针到链表尾部时，慢指针真好在倒数第N个节点；
2、需要特别注意的是，因为头节点也可能是要删除的点，所以需要new一个新的虚拟头结点-1，方便需要删除头结点的情况；
3、因为遍历结束后慢指针指向的是要删除的节点，链表节点无法自删除，所以新增一个比慢指针慢一步的指针，在找到待删除节点后，使用以下语句删除慢指针 
pre->next = pre->next->next;
完整代码如下 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // write code here
        ListNode* newHead = new ListNode(-1);
        ListNode* fast = head;
        ListNode* slow = head;
        newHead->next = head;
        ListNode* pre = newHead;
        for (int i = 0; i < n; i++) {
            fast = fast->next;
        }
        while (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
            pre = pre->next;
        }
        pre->next = pre->next->next;
        return newHead->next;
    }
};