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

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

1. 暴力法常规，倒数第N个，如果知道长度Len，那就是正数第Len - N + 1个。
2. 多一趟完整遍历，时间复杂度太高。“一般”情况倒数多少个如果倒着数数量不会太多，如果借用“栈”数据结构，在全部入栈之后，倒着数几个就OK。
3. 但是还是要一遍完整遍历+多几次，倒数第N个与末尾的距离，是不是可以利用下标0和下标N-1之间的距离表示，当N-1的那个指针遍历到末尾时，0那个指针遍历到目标位置。但是又是因为我们需要删除目标节点，所以要找到目标节点的前一个，方便删除。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode sentinel = new ListNode(-1, head);
        // 左右指针始终保持固定距离
        ListNode first = sentinel;
        ListNode second = sentinel;
        // 倒数 N + 1 个节点
        for (int i = 0; i < n + 1; i++) {
            first = first.next;
        }
        // first、second 同时移动
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return sentinel.next;
    }
}

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode sentinel = new ListNode(-1, head);
        ListNode cur = sentinel;
        // 定义一个栈
        Stack<ListNode> stack = new Stack<>();
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        // 弹栈
        for (int i = 0; i < n; i++) {
            stack.pop();
        }
        stack.peek().next = stack.peek().next.next;
        return sentinel.next;
    }
}

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 遍历链表得到长度
        int len = getLength(head);
        // 从前至后遍历，找到正数 len - n + 1 个元素
        // 定义哨兵
        ListNode sentinel = new ListNode(-1, head);
        ListNode cur = sentinel;
        for (int i = 0; i < len - n; i++) {
            cur = cur.next;
        }
        // 找到第 len - n 个节点
        cur.next = cur.next.next;
        return sentinel.next;
    }
    public static int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }
}