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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：
输入：head = [1], n = 1
输出：[]

示例 3：
输入：head = [1,2], n = 1
输出：[1]

需要删除结点，则需要先找到结点

假设链表有 n 个结点，倒数第 k 个节点就是正数第 n - k + 1 个结点

单链表只能顺序遍历，必须先遍历一遍，计算出 n ，然后再遍历链表计算第 n - k + 1 个结点

需要遍历两次链表才能得出倒数第 k 个结点

但是如果借用两个指针，则可以只遍历一遍链表即可得到倒数第 k 个结点

假设 k = 2，先让一个指针 p1 指向链表的头节点 head，然后走 k 步：

现在的 p1，只要再走 n - k 步，就能走到链表末尾的空指针了

此时，再用一个指针 p2 指向链表头节点 head：

接下来，让 p1 和 p2 同时向前走，
p1 走到链表末尾的空指针时前进了 n - k 步，
p2 也从 head 开始前进了 n - k 步，停留在第 n - k + 1 个节点上，
此时 p2 恰好停链表的倒数第 k 个节点上：

那么只遍历了一次链表，就获得了倒数第 k 个节点 p2：

/**
 * 查找倒数第 k 个结点：
 * 1）让 p1 和 p2 指向头结点
 * 2）让 p1 先走 k 步
 * 3）让 p1 和 p2 同时走，直至 p1 走到尾结点
 * 4）此时 p2 指向的结点就是倒数第 k 个结点
 *
 * @param head
 * @param k
 * @return
 */
ListNode findFromEnd(ListNode head, int k) {
    ListNode p1 = head;
    ListNode p2 = head;
    // p1 先走 k 步
    for (int i = 0; i < k; i++) {
        p1 = p1.next;
    }
    // p1 和 p2 同时走，直至 p1 走到尾结点
    while (p1 != null) {
        p1 = p1.next;
        p2 = p2.next;
    }
    // 此时 p2 指向第 n - k 个节点
    return p2;
}

而删除倒数第 n 个结点，则需要先找到倒数第 n+1 个结点，然后让倒数第 n+1 个结点指向第 n 个结点的下一个结点即可
此处需要借用虚拟结点，否则如果倒数第 n 个结点是头结点，在找倒数第 n+1 个结点时就出错了

/**
 * 删除链表的倒数第 N 个结点
 *
 * @param head
 * @param n
 * @return
 */
public ListNode removeNthFromEnd(ListNode head, int n) {
    // 借用虚拟结点
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    // 删除倒数第 n 个，要先找到倒数第 n+1 个结点
    ListNode x = findFromEnd(dummy, n + 1);
    // 删除掉倒数第 n 个结点
    x.next = x.next.next;
    return dummy.next;
}
/**
 * 查找倒数第 k 个结点：
 * 1）让 p1 和 p2 指向头结点
 * 2）让 p1 先走 k 步
 * 3）让 p1 和 p2 同时走，直至 p1 走到尾结点
 * 4）此时 p2 指向的结点就是倒数第 k 个结点
 *
 * @param head
 * @param k
 * @return
 */
ListNode findFromEnd(ListNode head, int k) {
    ListNode p1 = head;
    ListNode p2 = head;
    // p1 先走 k 步
    for (int i = 0; i < k; i++) {
        p1 = p1.next;
    }
    // p1 和 p2 同时走，直至 p1 走到尾结点
    while (p1 != null) {
        p1 = p1.next;
        p2 = p2.next;
    }
    // 此时 p2 指向第 n - k 个节点
    return p2;
}