1. Description

Given the head of a linked list, remove the nth node from the end of the list and return its head.
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
Follow up: Could you do this in one pass?

2. Analysis

删除倒数第n个节点有些麻烦，自然想到删除正数第n个节点较为简单，故可以反转链表后删除第n个节点再反转链表。但follow up要求one pass，反转链表的方法需要遍历两次链表加上删除第n个节点的一次遍历共三次遍历。
本题难点在于如何在one pass的时候就让指针移动到待删除节点的前节点。因为一般情况下遍历链表采用while循环，结束条件为pointer.next == null，此时并无其他指针存在。解决方案为采用双指针，我们希望fast指针指向尾结点时，slow指针指向待删除节点的前节点，此时fast和slow相隔n个节点。故一开始就让fast指针先走n个节点，再让fast和slow同步移动即可至fast指向尾结点即可。
注意：让fast指针先走n个节点时，由于1 <= n <= sz，fast可能移动sz步到达null，无法再与slow同步移动，此时说明删除倒数第sz个节点即头节点，故直接return head.next即可。

3. Code

class Solution{
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head;
        while(n-- > 0){
            fast = fast.next;
        }
        if(fast == null) return head.next;
        ListNode slow = head;
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}