题解 | #删除链表的倒数第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) {
        // write code here
        ListNode *res = new ListNode(0);
        res->next = head;
        ListNode *pre = res;
        ListNode *fast = head;
        ListNode *slow = head;
        for(int i = 0;i<n;i++)
        {
            if(fast == nullptr)
                return head;
            fast = fast->next;
        }
        while(fast)
        {
            fast = fast->next;
            slow = slow->next;
            pre = pre->next;
        }
        pre->next = slow->next;
        return res->next;
    }
};

解题思路：使用三个指针，快指针、满指针、前序指针

具体做法：

• step 1：给链表添加一个表头，处理删掉第一个元素时比较方便。
• step 2：准备一个快指针，在链表上先走n步。
• step 3：准备慢指针指向原始链表头，代表当前元素，前序节点指向添加的表头，这样快慢指针之间相距就是一直都是n。
• step 4：快慢指针以及前序指针同步移动，当快指针到达链表尾部的时候，慢指针正好到了倒数n个元素的位置。
• step 5：最后将该节点前序节点的指针指向该节点后一个节点，删掉这个节点。