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

思路

双指针，同等速度，但是出发点不一样（fast比slow多走n-1步骤）

注意要考虑到前一个节点，
注意要释放节点，拒绝内存泄漏
注意要设置一个哑巴节点，使算法具有普适性

代码

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* removeNthFromEnd(ListNode* head, int n) {

        /*
        if(head==nullptr) return nullptr;

        // write code here

        // 倒数第n个节点 = 正数第k+1-n个，k为节点个数

        ListNode* cur = head;
        int count = 0;
        while(cur!=nullptr){
            cur = cur->next;
            count++;
        }

        ListNode* dum = new ListNode(0);
        dum->next = head;

        ListNode* ptr = dum;
        // 这样变成了删除K+2-n个指针，先找到k+2-n-1个指针
        for(int i = 1; i<=count-n;i++){
            ptr = ptr->next;
        }

        ListNode* nex = ptr->next;
        ptr->next = nex->next;
        free(nex);

        return dum->next;
        */

        // 双指针法
        ListNode* dump = new ListNode(0);
        dump->next = head;

        ListNode* slow = dump;
        ListNode* fast = dump;

        // fast指针先走n-1步
        for(int i = 1; i<=n+1; i++){
            fast = fast->next;
        }
        while(fast!=nullptr){
            fast = fast->next;
            slow = slow->next;
        }

        slow->next = slow->next->next;

        return dump->next;


    }
};