删除链表的第n个结点

**图解：

链接

思路：

1.由于对于删除操作：对于首节点的删除与其他结点删除是不一样的操作，所以为了同一操作

2.可以设置一个虚的头结点，将虚的头结点指向原链表的头结点

3.设置两个指针：快指针fast和慢指针slow,赋值为首地址

4.由于要进行删除操作，所以需要保存需要删除的节点的前一个节点的地址

5.先让fast指针移动n位，再让三个指针一起移动，注意slow和pre的更新顺序，直到fast到达了null

代码：

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    public ListNode removeNthFromEnd (ListNode head, int n) {
        //由于对于删除操作：分为两种情况1.删除头结点2.删除非头结点
        //所以为了方便同一操作，可以先设置一个虚的头结点，将虚的头结点连接到表头
        ListNode dummynode=new ListNode(-1);
        dummynode.next=head;
        //设置三个指针：快指针fast和慢指针slow，记录slow的前一个节点的指针pre（用于后面的删除节点操作）
        //fast和slow都是指向原来的表头，pre赋值虚节点的地址
        ListNode fast=head;
        ListNode slow=head;
        ListNode pre=dummynode;
        //先让fast指针移动n步
        for(int i=1;i<=n;i++){
            fast=fast.next;
        }
        //再让三个指针同步移动，注意顺序先要保留pre=slow，再让slow赋值为后一个节点
        while(fast!=null){
            fast=fast.next;
            pre=slow;
            slow=slow.next;
        }
        //删除倒数第n个节点，就是将pre指向删除的节点的下一个节点
        pre.next=slow.next;
        //返回原来的表头：dummnode.next
        return dummynode.next;
    }
}