题目
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例一：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]示例二：
代码语言：javascript复制输入：head = [1], n = 1
输出：[]示例三：
代码语言：javascript复制输入：head = [1,2], n = 1
输出：[1]提示：
提示：
- 链表中结点的数目为
sz 1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz进阶：你能尝试使用一趟扫描实现吗？
解题
解法一
思路
为了实现一趟扫描，我的思路想法是首先，遍历链表，将链表的每个地址都存入ArrayList中，然后遍历完毕后，得出链表长度，得出需要删除结点的地址，然后直接去ArrayList中对应的索引处的地址删除即可。
解决
代码语言：javascript复制class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//遍历链表，将链表的每个地址都存入ArrayList中，然后遍历完毕后，得出链表长度，得出需要产出结点的地址，然后直接去ArrayList中对应的索引处的地址删除即可。
//声明ArrayList用来存地址
ArrayList arr = new ArrayList<>();
//记录节点数，结点数默认为1
int num = 0;
//声明移动结点node，初始为head
ListNode node = head;
//开始遍历链表
while(node!=null){
arr.add(node);
node = node.next;
num ;
}
//判断要删除的结点是不是最后一个
if(num==n){ //判断要是删除的是头节点
head = head.next;
}else if(n==1){ //表示需要删除的是最后一个结点
arr.get(num-2).next = null;
}else{
//表示删除的是中间结点找到需要删除结点的前一个，((num 1)-n)-1索引为需要删除的结点
arr.get(((num 1)-n)-2).next = arr.get(((num 1)-n));
}
return head;
}
}结果
代码语言：javascript复制> 2023/07/15 15:59:55
解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.7 MB,击败了23.83% 的Java用户解法二（来自LeetCode官方）
思路
使用双指针的方法，我们需要找到倒数第n个结点，可以使用两个指针first和second同时对链表进行遍历，并且first比second超前n个结点，当first遍历到链表的末位时，second恰好处于倒数第n个结点。
具体的，初始时，first和second均指向头结点，使用first对链表进行遍历，当遍历次数为n时，此时first和second间隔了n-1结点，即first比second超前了n个结点。然后两个指针同时继续前进，当first到达链表末尾的时候second恰好指向倒数第n个结点
解决
代码语言：javascript复制class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
ListNode first = head;
ListNode second = dummy;
for (int i = 0; i < n; i) {
first = first.next;
}
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
ListNode ans = dummy.next;
return ans;
}
}
//作者：LeetCode-Solution
//链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/结果
- 时间复杂度：O(L)，L是链表的长度；
- 空间复杂度：O(1)。
