躬行算法之删除链表的倒数第N个节点

Leetcode P19.

这道题目，需要注意，这里的链表是单向链表。因为没有逆向指针，所谓“倒序第 n 个节点”，便无从说起。我们可以转换思路，倒序第 n 个节点，在一个大小为 sz 的链表中，同时也会是正序第 sz+1-n 个节点。
遍历链表，同时计数 i，直到末尾, i==sz，此过程中可能出现如下情况：

1. 遍历部分不够长，第 i+1-n 个节点尚未出现，即 i+1-n <= 0，
2. 遍历部分长度达到临界值，第 i+1-n 个节点恰好出现，即首次出现 i+1-n > 0；
3. 遍历部分足够长，直到末尾，第 i+1-n 个节点在游标指针的落后位置，也就是更靠近链表 head 的位置，当然此过程中的 i+1-n > 0 依然是成立的。

基于这种思路，考虑使用快慢指针，快指针指向链表尾部，遍历链表，慢指针指向目标节点。在这个题中，因为还要移除目标指针，所以还需要一个额外的指针，指向目标节点的 prev 节点，该指针应滞后一步于慢指针。

各指针移动过程如下：

1. 快指针先移动，i 随着快指针的移动渐增，慢指针尚未开始移动；
2. 快指针移动，直到临界点，正序第 sz+1-n 个节点出现，此时 i+1-n > 0 ，此时慢指针准备开始移动，指向 head；
3. 快慢指针移动，滞后一步于慢指针的 prev 指向旧的慢指针，也开始移动；
4. 快、慢、滞后指针分别移动，直到快指针遍历完整个链表，三个指针停止移动；

此时，判断慢指针即为待移除的节点。判断慢指针处于的几种状态即可：
慢指针从未移动（slow==null）、
慢指针恰巧指向第一个节点而滞后指针尚未有指向（slow==head && prev==null）、
慢指针移动到某个未知而之后指针也已开始移动（slow!=null && prev!=null）。

最后根据分析，写出代码：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head;
        ListNode slow = null; // 目标节点
        ListNode prev = null;
        int i = 1;
        while (fast != null) {
            fast = fast.next;
            i++;
            if (i + 1 - n > 0) {
                if (slow == null) {
                    slow = head;
                } else {
                    prev = slow;
                    slow = slow.next;
                }
            }
        }
        if (slow == null) {
            return head;
        }
        if (prev == null) {
            return slow.next;
        } else {
            prev.next = slow.next;
            return head;
        }
    }
}


链表节点结构定义

```java
class ListNode {
    int val;
    ListNode next;

    ListNode() {}

    ListNode(int val) { this.val = val; }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}