Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example, Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note: Given n will always be valid. Try to do this in one pass.

经典问题距离尾部Nth元素的衍生题。用快慢指针，快的指针先移动n位，然后同时移动快慢指针直到快的指针指向尾部最后一个元素。 这时候慢指针的下一个元素就是距离尾部第N位。（需要定位距离尾部n-1位，方便删除）

需要小心的是如果头部元素就是要删除的那个，例如[1] n=1。这种情况下要判断tail移动n位后是否已经移出尾部。

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