【题解】剑指 Offer II 021. 删除链表的倒数第 n 个结点（双指针）（快慢指针）

题目链接

 力扣

题目描述

给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：

输入：head = [1], n = 1
输出：[]
示例 3：

输入：head = [1,2], n = 1
输出：[1]
 

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

解题思路

利用快慢指针，因为头结点需要特殊处理，所以可以一开始就在头节点前面插入一个节点，然后最终结果返回head->next即可

一开始设置slow在新创建的头结点上，fast在初始的头结点上，至于为什么不一开始让初始的fast节点和slow节点位置相同，是因为本体是要删除节点，应该找到被删除节点的前一个节点才可以完成删除操作，只找到要被删除的节点无法完成

删除倒数第n个节点，就先让fast向后走几位

假设n=2，则移动后为

然后slow和fast同时向后移动，当fast==NULL的时候说明slow已经走到了要求被删除节点的前一个节点，只需要将slow->=slow->next->next即可 

题解

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* fast=head;
        ListNode* ans=new ListNode(0,head);
        ListNode* slow=ans;
        int i=0;
        while(fast&&inext;
            i++;
        }
        while(fast){
            slow=slow->next;
            fast=fast->next;
        }
        slow->next=slow->next->next;
        return ans->next;
    }
};