🤔|LeetCode019|删除链表的倒数第N个结点

Table of Contents

难度：Medium🤔

题目 #

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
```
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
```

思路 #

双指针：如果要删除倒数第k个node，只需要让快指针提前移动k-1个node，这样当快指针移动到最后一个node（即其next=nullptr）时，慢指针就是待删除的node。为了完美地删除一个node，还需要记录一个前驱结点last，它始终是slow的上一个节点。
额外头结点法：考虑以下情况：
- ```
输入：head = [1], n = 1
输出：[]
```
- 因为初始化last为head，所以如果只有一个node，则无法正确地删除node。此时可以额外加一个头结点哨兵flag，让他的next初始化为head，然后一开始把last初始化为flag即可。最后返回整个链表时，只需要返回flag->next即可。

代码实现 #

 #include <leetcode.h>

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* slow=head,*fast=head,*last=new ListNode(0,head);
        ListNode* flag=last;
        for(int i=1;i<=n-1&&fast->next;i++)
            fast=fast->next;
        while(fast->next!=nullptr){
            fast=fast->next;
            last=slow;
            slow=slow->next;
        }
        // cout<<slow->val<<endl;
        last->next=slow->next;
        return flag->next;
    }
};