题解 | #删除链表的倒数第n个节点#

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

备注：
题目保证 n一定是有效的
请给出请给出时间复杂度为O(n) 的算法

思路（通俗易懂版）：
这题首先大家想的思路就是求出这个链表的长度length，
然后根据运算知道倒数第n个字母对应的的正序排序是第 length-n+1 个元素
然后创建两个指针，一个cur指针（指向需要删除的结点），一个pre指针（用pre的next指向cur的next）就可以啦。
然后我们返回头指针即可。
等等 好像哪里不对劲
如果删除的是头指针直接返回是不对的，所以判断一下删除的是不是头指针就可以啦
（根据n 和length的值是不是很容易判断。）
C++代码:

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // write code here
        int length=0;
        ListNode *phead= head;
        while(phead)   //求出长度
        {
            length++;
            phead=phead->next;
        }
        if(length==n)     //删除的是头结点直接返回头结点的下一个节点就好啦
            return head->next;

        ListNode *pre=head,*cur=head;
        int step=length-n;
        while(step--)
        {
            cur=cur->next;
              if(step==1)
                pre=cur;
        }
        pre->next=cur->next;
        cur->next=nullptr;
        return head;
    }
};