[数据结构与算法]leetcode 19. 删除链表的倒数第 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

进阶：最好使用一趟扫描实现。

思路：
使用双指针可以只遍历一遍。
常规思路是先遍历一遍得出链表的结点总数，再根据n值遍历找到要删除的前一个结点，对前一个结点的next指针进行操作。

用快慢指针可以先让快指针走n步，等快指针到达被删除的结点时，快慢指针再同时前进，指向下一个结点，当快指针到达最后一个结点时，判断条件为 fast->next==NULL ，退出循环，此时慢指针的位置就是要被删除的结点的前一个位置。

当然，对于特殊情况我们肯定也要特殊考虑，比如只有一个结点时返回NULL就行了，如果要删除第一结点时，最后 fast 指针一定指向 最后一个结点的next，即 NULL。

代码：

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *slow=head,*fast=head;
        if(!head&&!head->next)
            return NULL;
        for(int i=0;i<n;++i)
            fast=fast->next;
        if(!fast)
            return head->next;
        while(fast->next){  //用fast->next判断是不是最后一个结点
            slow=slow->next;
            fast=fast->next;
        }
        slow->next=slow->next->next;
        return head;
    }
};

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head==null&&head.next==null)
            return null;
        ListNode slow=head,fast=head;
        for(int i=0;i<n;++i)
            fast=fast.next;
        if(fast==null)
            return head.next;
        while(fast.next!=null){
            slow=slow.next;
            fast=fast.next;
        }
        slow.next=slow.next.next;
        return head;
    }
}