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]

提示：

• 链表中结点的数目为 size
• 1 <= size <= 30
• 0 <= Node.val <= 100
• 1 <= n <= size

进阶：你能尝试使用一趟扫描实现吗？

解题思路

如果题目不要求我们只遍历一遍链表，但要求空间复杂度复杂度为 O(1) 的话，我们该怎么做呢？

我们往往不容易一开始就想到特别好的做法，暴力一点也无妨。

我的思路：

1. 遍历一遍链表，同时计数，可以得到链表的总长度 size
2. 那么我们需要倒数第 n 个元素，其实就是顺数第 size - n + 1 个元素
3. 再遍历一遍链表，同时计数，但这次我们目标明确，找到第 size - n + 1 个元素
4. 剩下的就是普通的删除链表内某节点的操作了

代码此处略去，但是复杂度应该是：

• 时间复杂度：O(2 * n) = O(n)，因为遍历了两遍链表
• 空间复杂度：O(1)

这种做法空间复杂度很低，但没有满足题目要求只遍历一趟数组的要求。

我们能不能不预处理链表的长度呢？毕竟一趟遍历只为了一个 size，多少有点不值得。

双指针法

由于我们需要找到倒数第 n 个节点，因此我们可以使用两个指针 left 和 right 对链表进行遍历。

right 先从头到尾对链表进行遍历，当遍历到第 n 个节点的时候，我们要注意到一个点：此时剩下多少个元素没有遍历呢？答案是 size - n 个。

我们要删除的，是顺数第几个元素呢？刚好也是第 size - n + 1 个。

那么这个时候，让 left 也从链表头出发，两个指针开始同步往右边遍历，如此一来，当 right 指针走完剩下的 size - n 步时，left 指针也就走到了第 size - n 个元素。

尽管对于 指针位置信息 的处理可能得更加细致，但上述思路很清晰地表明我们可以找到需要删除的目标节点，而且 right 指针只需要走 size 步，left 指针只需要走 size - n 步，满足了题目一趟遍历的要求，同时空间复杂度也来到了常数级。

记住，我们设置快慢指针的目的是：让快慢指针相差 n 个结点，快指针走到尾部的时候，慢指针刚好处于倒数第 n 个节点的位置。

我的代码

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //虚拟头节点
        ListNode dummy = new ListNode(0, head);
        ListNode left = dummy;
        ListNode right = dummy;
        //right 走到第 n 个元素的位置
        for (int i = 0; i < n; i++) {
            right = right.next;
        }
        //left 开始和 right 同步移动
        while (right.next != null) {
            left = left.next;
            right = right.next;
        }
        //要删除的是 left 的后一个节点
        left.next = left.next.next;
        return dummy.next;
    }
}

时间复杂度：O(n)

空间复杂度：O(1)

总结

如果使用 C，C++ 编程语言的话，不要忘了还要从内存中删除这两个移除的节点。

当然如果使用 Java ，Python 的话就不用手动管理内存了。

注意虚拟头节点的引入，可以使代码逻辑更统一。