/**
 * 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; }
 * }
 */
// 思路：快慢指针，快指针先走n步
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 虚拟头节点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        // 快指针先走n步
        ListNode fast = dummy, slow = dummy;
        while(n -- > 0){
            fast = fast.next;
        }// 结束后在fast在第n个节点

        //直到fast节点指向最后一个节点
        while(fast.next != null){
            slow = slow.next;
            fast = fast.next;
        }// 结束后slow节点指向倒数第n + 1个节点

        slow.next = slow.next.next;// 删除倒数第n个节点

        return dummy.next;
    }
}
/*
case：
1 2 3 4 5 （n=3）
-1 1 2 3 4 5 dummy->-1
fast -> 3
fast -> 5, slow->2
del 3
*/