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

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

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummyhead = new ListNode(0);
        dummyhead->next = head;
        ListNode *tmp = head;
        for (int i = 0; i < n; ++i) {
            tmp = tmp->next;
        }
        ListNode *bef = dummyhead;
        while (tmp) {
            tmp = tmp->next;
            bef = bef->next;
        }
        ListNode *nxt = bef->next;
        bef->next = bef->next->next;
        delete nxt;
        return dummyhead->next;
    }
};

可以先遍历一遍计算出链表长度，然后再计算出正数的节点位置，进行删除。

一遍遍历删除的思路：先用fast指针找到正数第k个，然后用slow指针指向头部，与fast指针同时移动，这样fast指针移动到最后一个节点，slow指针就会指向倒数第k个。

* 删除节点需要找到该节点的上一个节点bef，我们要把slow当作bef，所以slow要往前一位。

* 然而head不能再往前一位了，所以用一个dummyhead作为虚假头节点。

* dummyhead还有个好处，就是如果删除的是head，不需要额外处理指向新的head。