19. 删除链表的倒数第N个节点

解法一：一次遍历+数组存储

用数组存储遍历过的点，根据索引得到第N个结点和它的前驱结点，然后进行删除操作。注意考虑边界情况。

/**
 * 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; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return head;
        }
        List<ListNode> list = new ArrayList<>(n);
        ListNode p = head;
        while (p != null) {
            list.add(p);
            p = p.next;
        }
        if (list.size() > n) {
            ListNode toDeleteNode = list.get(list.size() - n);
            ListNode preNode = list.get(list.size() - n - 1);
            preNode.next = toDeleteNode.next;
            toDeleteNode = null;
        } else {
            p = head;
            head = head.next;
            p = null;
        }
        return head;
    }
}

解法二：一次遍历+快慢指针

在第一个结点前面再创建一个头指针，作为慢指针的出发点，快指针以第一个结点为出发点，先走 n 步，然后慢指针和快指针一起遍历。这样，当快指针走到终点时，慢指针位于倒数第 N 个结点的前驱。

/**
 * 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; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if ((head == null) || (head.next == null)) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = new ListNode(0, head);
        head = slow;
        for (int i = 0; i < n; ++i) {
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head.next;
    }
}