leetcode 19. 删除链表的倒数第N个节点

快慢指针1（带头结点）

让快慢指针相差n个位置，当快指针到最后一个元素时，慢指针的下一个元素正好就是要删除的元素
ps：不用特殊考虑删除头结点的情况

代码

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {  

    ListNode *start = new ListNode(-1);             //建立一个新的头结点
    start->next = head;
    ListNode *slow = start , *fast = start , *temp; 

    for(int i = 1; i <= n ; i++)    fast = fast->next;
    
    while(fast->next)
    {
        slow = slow->next;
        fast = fast->next;
    }

    temp=slow->next;
    slow->next=slow->next->next;
    delete temp;
    
    return start->next;             //head可能被删除了，所以用start->next表示新的头结点
    }

};

快慢指针2（不带头结点）

让快慢指针相差n个位置，当快指针到最后一个元素时，慢指针的下一个元素正好就是要删除的元素
ps：特殊考虑了n为链表元素个数的情况，此时要删除的是头结点，让头结点的下一个节点作为新的头结点

代码

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode *slow = head , *fast = head; 
    ListNode *temp;

    for(int i = 1; i <= n ; i++)    fast = fast->next;
    
    if(fast == NULL)            //只有当要删除头结点时，fast==NULL，n恰好等于链表的元素个数
    {
        temp = head->next;
        delete head;
        return temp;            //返回新的头结点
    }
    while(fast->next)
    {
        slow = slow->next;
        fast = fast->next;
    }

    temp=slow->next;
    slow->next=slow->next->next;
    delete temp;
    
    return head;
    }
};

方法3 递归【转载】

在讨论区看到的一位大佬的解答，感觉很棒

ps：递归cur每次++表示当前是倒数第几个节点，如果为n的话，让上一个节点指向自己的下一个节点，则达到删除当前节点的效果
@smart067

代码

class Solution {
public:
    int cur=0;
    ListNode* removeNthFromEnd(ListNode* head, int n) {
       if(!head)        return NULL;
       head->next = removeNthFromEnd(head->next,n);

       if(n == ++cur)   return head->next;              
       return head;
    }
};