4.删除链表的倒数的第N个节点

19.删除链表的倒数第N个节点

4.1题目

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

• 示例一：

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

• 示例二：

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

• 示例三：

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

4.2解法：双指针

• 该题为双指针的应用：如果要删除倒数第n个节点，则先让fast移动n+1步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了

• 问题：fast首先走n + 1步 ，为什么是n+1呢
• 因为只有这样同时移动的时候 slow才能指向删除节点的上一个节点（方便做删除操作）

• fast和slow同时移动，直到fast指向末尾，如题：

• 删除slow指向的下一个节点，如图：

	public ListNode removeNthFromEnd(ListNode head, int n) {
        
        ListNode  dummy=new ListNode(-1,head);
        ListNode  slow=dummy;
        ListNode  fast=dummy;

        //1、先让fast走 n+1 步
        for(int i=0;i<=n;i++){
            fast=fast.next;
        }

        //2、让fast、slow同时移动，直到fast到末尾为空
        while(fast!=null){
            slow=slow.next;
            fast=fast.next;
        }
        
        //3、删除该元素
        slow.next=slow.next.next;

        return dummy.next;
    }