题目描述
给你一个链表，删除链表的倒数第 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]提示：
- 链表中结点的数目为
sz 1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
思路
在对链表进行操作时，一种常用的技巧是添加一个哑结点（dummy node），它的next指针指向链表的头结点。这样就不需要对头结点进行特殊的判断。
例如，在本题中，如果要删除节点y，需要知道节点y的前驱节点x，并将x的指针指向y的后继节点。但由于头结点不存在前驱节点，在删除头结点时需要进行特殊判断。但如果添加了哑结点，那么头节点的前驱节点就是哑结点本身，此时只考虑通用情况即可。
方法一：计算链表长度
首先从头节点开始对链表进行一次遍历，得到链表的长度L。随后再从头结点开始对链表进行一次遍历，当遍历到第L-n+1个节点时，就找到了要删除的节点。
为了方便删除操作，可以从哑结点开始遍历L-n+1个节点。当遍历到第L-n+1个节点时，它的下一个节点就是需要删除的节点，这样只需要修改一次指针，就能完成删除操作。
代码略。
时间复杂度：O(L)
空间复杂度：O(1)
方法二：栈
在遍历链表的同时将所有节点依次入栈。根据栈【先进后出】的原则，弹出栈的第n个节点就是需要删除的节点，并且栈顶的节点就是待删除节点的前驱节点。
代码略。
时间复杂度：O(L)
空间复杂度：O(L)
方法三：双指针
以上两种方法一种多次遍历了链表，一种空间复杂度与链表长度有关。
可以使用两个指针first和second同时对链表进行遍历，并且first比second超前n个节点。当first遍历到链表的末尾时，second就恰好处于倒数第n个节点。
具体地，初始时first和second均指向头结点。首先使用first对链表进行遍历，遍历的次数为n。此时，first和second之间间隔了n-1个节点，即first比second超前了n个节点。在此之后，同时使用first和second对链表进行遍历。当first遍历到链表的末尾（即first为空指针）时，second恰好指向倒数第n个节点。
如果能够得到倒数第n个节点的前驱节点而不是倒数第n个节点的话，删除操作会更加方便。因此可以考虑在初始时将second指向哑结点，其余的操作步骤不变。这样一来，当first遍历到链表的末尾时，second的下一个节点就是需要删除的节点。
如果second初始指向head，写出的代码如下，可以看到需要有一个pre节点指向second的前驱节点：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode tmpHead = new ListNode();
tmpHead.next = head;
ListNode pre = tmpHead;
ListNode fast = head, low = head;
for (int i = 0; i < n && fast != null ;i++){
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
low = low.next;
pre = pre.next;
}
pre.next = low.next;
return tmpHead.next;
}
}如果second初始指向哑结点，写出的代码如下，不需要额外的节点记录前驱节点：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode tmpHead = new ListNode();
tmpHead.next = head;
ListNode fast = head, low = tmpHead;
for (int i = 0; i < n && fast != null ;i++){
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
low = low.next;
}
low.next = low.next.next;
return tmpHead.next;
}
}