一、题目描述
给你一个链表，删除链表的倒数第 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
二、思路分析
先从最简单的思路说起，想要知道倒数第几个节点的位置，首先要知道链表长度信息。
但是从题目信息，我们只得知这是一个单链表，并不知道它的长度信息。
这时候就可以考虑先遍历一遍链表的节点，统计一下链表的长度，然后再计算出节点在链表中的位置，这时候就用这个节点的前驱节点指向它的后继节点。
但是这里面有一个点要注意一下，如果删除的是头节点该怎么处理
代码实现
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
// 计算链表长度
int length = 0;
ListNode temp = head;
while (temp != null) {
++length;
temp = temp.next;
}
// 增加前置节点，防止删除第一个元素
ListNode ans = new ListNode(0, head);
temp = ans;
// 计算出要删除节点在链表中的位置
for (int i = 1; i < length - n + 1; i++) {
temp = temp.next;
}
temp.next = temp.next.next;
return ans.next;
}
}从代码实现中，我们可以看出空间复杂度为O(1)，时间复杂度为O(n)
那么是不是还有更加优雅的方法呢？
小伙伴们，优雅的方法肯定是有的，就看你怎么理解这个了……
假设倒数第K个节点就是尾节点，那么我们只要把指针指向它的前驱节点即可，不需要在进行第二次扫描处理。
那么如何制造出倒数第K个节点就是尾节点的错觉呢？这就不的不请出两只小白兔了，假如在一条笔直笔直的小路上，我们让两只速度一样的小白兔赛跑，让其中的一只先跑K米，然后在再让另一只小白兔起跑……
那么请问一下，当先跑的那只小白兔到达终点的时候，另一个小白兔离终点还有多少米？
没错，这就是这题的关键思路，两只兔子解法~~~
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head.next == null) {
return null;
}
ListNode first = head;
ListNode second = head;
while (n > 0) {
first = first.next;
--n;
}
if (first == null) {
return head.next;
}
while (first.next != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return head;
}
}从代码实现中，我们可以看出空间复杂度为O(1)，时间复杂度为O(n)
三、总结
关于链表的问题，基本上就是通过遍历链表解决问题，一次遍历不够就两次。此时我们可以使用空间换时间的策略，可以优先考虑是否能用多个指针，每个指针代表一次遍历，从而减少遍历的次数，提高查询效率。
