快慢指针删除链表的第N个元素——力扣19

快慢指针删除链表的第N个元素——力扣19"/>

快慢指针删除链表的第N个元素——力扣19

给你一个链表，删除链表的倒数第 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]

分析：

想要删除倒数第n个节点，我们必须找到倒数第n+1个节点，即倒数第n节点的前驱节点

思路 ：

创建两个指针 fast和slow，让fast指针先走n+1步，然后slow和fast一起移动，然后当fast移动到最后一个节点时，slow此时指到倒数n+1节点，此时便可以执行删除操作

 public ListNode removeNthFromEnd(ListNode head, int n) {if(head==null){return null;}ListNode duty=new ListNode(0);duty.next=head;ListNode fast=duty;   ListNode slow=duty;for(int i=0;i<=n;i++){fast=fast.next;}while(fast!=null){fast=fast.next;slow=slow.next;}slow.next=slow.next.next;return duty.next;}

 之所以new一个duty让他的后继节点指向head，是因为有可能存在head节点被删除的情况，此时如果直接返回head会出现指针指空的问题，返回duty.next可以有效解决空指针问题