题目描述
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
示例 2：
示例 3：
提示：
- 链表中结点的数目为 sz
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
题目解析
要删除倒数第 n 个节点，就得获得倒数第 n + 1 个节点的引用。
获取单链表的倒数第 k 个节点，就是想考察 双指针技巧 中快慢指针的运用，一般都会要求你只遍历一次链表，就算出倒数第 k 个节点。
- 第一步，我们先让一个指针 p1 指向链表的头节点 head，然后走 k 步
- 第二步，用一个指针 p2 指向链表头节点 head：
- 第三步，让 p1 和 p2 同时向前走，p1 走到链表末尾的空指针时走了 n – k 步，p2 也走了 n – k 步，也就是链表的倒数第 k 个节点：
这样，只遍历了一次链表，就获得了倒数第 k 个节点 p2。
解法中在链表头部接一个虚拟节点 dummy 是为了避免删除倒数第一个元素时出现空指针异常，在头部加入 dummy 节点并不影响尾部倒数第 k 个元素是什么。
参考代码
以下为 Java 代码。
复杂度分析
- 时间复杂度：O(L)，其中 L 是链表的长度。
- 空间复杂度：O(1)。
