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

题目：

题解：

思路：
第一次遍历计算链表长度
第二次遍历使用三个指针：
pre：指向p前一个
p：工作指针，直到p指向count==size-n+1位置（即要删除的结点）
pnext：p的下一个
删除p即可

**注意：**力扣里的链表的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:
    ListNode* removeNthFromEnd(ListNode* head, int n) {

        //注意，这个head也存数据，不是单纯的头结点

        //1:第一次遍历:计数,求出size
        int size=0;
        ListNode* p=head;
        while(p!=nullptr)
        {
            size++;
            p=p->next;
        }

        //处理特殊情况，第一种特殊情况：要删除第一个结点
        if(size==n)
        {
            ListNode* result=head->next;
            delete head;
            return result;
        }

        //2:删除倒数第n个结点
        ListNode* pre=head;
        p=head;
        int count=1;//p所指的结点编号，从1开始


        
        while(size-n+1!=count)
        {
            pre=p;
            p=p->next;//向前移动
            count++;
        }

        ListNode* pnext=p->next;
        pre->next=pnext;
        delete p;

        //处理特殊情况，第二种特殊情况：只有一个结点
        if(size==1)
        {
            return nullptr;
        }
        
        return head;

    }
};