19. Remove Nth Node From End of List

naive方法，要算两次，正数=总数(length)+1-倒数(n)，所以走到倒数前面一个节点也就是length-n修改指针指向。

public ListNode removeNthFromEnd(ListNode head, int n) {
    if (head == null || n == 0) return null; // 注意head为空或者list为0返回null
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode res = dummy;

    // compute length
    int length = 0;
    ListNode l1 = head;
    while (l1 != null) {
        length++;
        l1 = l1.next;
    }
    if (n > length) return null; // 如果要找的倒数数字大于链表的总长度，返回空

    // forward steps
    int step = length - n;
    for (int i = 0; i < step; i++) {
        dummy = dummy.next;
    }
    dummy.next = dummy.next.next;
    return res.next;
}

高票答案改写：快慢指针

def removeNthFromEnd(self, head, n):
    """
    :type head: ListNode
    :type n: int
    :rtype: ListNode
    """
    if not head or not n: return None 
    dummy = ListNode(0)
    dummy.next = head
    fast, slow = dummy, dummy

    for i in range(n + 1):
        if fast.next:
            fast = fast.next
        else: 
            return None

    while fast:
        fast = fast.next
        slow = slow.next

    slow.next = slow.next.next
    return dummy.next

边界如图，可以写成两种情况

第二种：

for i in range(n):
    if fast.next:
        fast = fast.next
    else: 
        return None

while fast.next:
    fast = fast.next
    slow = slow.next