[数据结构与算法]LeetCode 算法 19：删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 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]

双指针，一个慢的指向快的后n个，等到快指针走到尽头，慢指针正好是指向要删除的地方。
需要处理特殊情况

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        
        ListNode* fast=head;
        ListNode* low=head;
        ListNode*p=head;
        for(int i=0;i<n;i++)
            fast=fast->next;
        while(fast!=nullptr)
        {
            p=low;
            low=low->next;
            fast=fast->next;
        }
        if(p==low)//特殊情况
            return p->next;
        p->next=low->next;
        return head;
    }
};

使用递归
递归配合全局变量寻找所要删除的数，找到之后将其删除

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int c=0;
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head==nullptr)
            return nullptr;
        head->next=removeNthFromEnd(head->next,n);//1
        c++;//2 这两步的顺序很重要，这样是删除倒数的数
        //通过递归实现从后往前数
        if(c==n)
            return head->next;//找到就将其删除
        return head;//不是要删除的数就不动
    }
};