LeetCode刷题Java版019.删除链表的倒数第 N 个节点
作者：沉默王二
发布时间：2022-08-05T16:00:35.182+0800
019.删除链表的倒数第 N 个节点
题意
给你一个链表，删除链表的倒数第 n 个节点，并且返回链表的头节点。
难度
中等
示例
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
分析
题意很清楚，就是要我们删除对应的节点，首先需要找到这个节点，我们可以遍历整个链表，获得整个链表的长度，然后再找到倒数第 n 个节点。
找到了这个点之后，我们就可以定位到它的上一个位置。
对于链表节点的删除，设p节点为待删除节点，那么我们只需要获得p的上一个节点，然后把这个节点的下一个节点指向p.next 即可。
图示流程如下：
所以本题就是很纯粹的模拟。
ava
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
int siz = 0;
ListNode realhead = new ListNode(0,head);
ListNode pos = head;
while(pos != null){
siz++;
pos = pos.next;
}
pos = realhead;
for(int i = 1;i < siz - n + 1;i++)
pos = pos.next;
pos.next = pos.next.next;
return realhead.next;
}
}
效率也非常不错。
这道题目最后有一个小小的要求，问我们能不能“尝试使用一趟扫描实现？”
实际上一趟扫描是不太可能的，Leetcode官方给出的双下标的解法其实并不是一趟扫描，它利用了两个下标，第一个下标比第二个下标更靠前n个位置，这样子就可以通过所谓的一趟扫描解决，但是实际上，观察上述过程，两个下标加起来的移动次数还是没有变化，只是相当于将我们求长度以及寻找倒数第n 个点的两个循环写到了一起，实际的运行效率并没有提高，运算次数仍然一样。
总结
链表是除了数组之外，我们接触到的另外一个数据结构，对于它的增删改查，我们必须得了如指掌，因为它们是计算机用来存储数据单元的最基本的容器，即便计算机的学习是一个自顶向下的过程，但在掌握了顶层之后，我们应该一点点深挖下去，才能百尺竿头更进一步。
力扣链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
## 019.删除链表的倒数第 N 个节点
题意
给你一个链表，删除链表的倒数第 n 个节点，并且返回链表的头节点。
难度
中等
示例
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
分析
题意很清楚，就是要我们删除对应的节点，首先需要找到这个节点，我们可以遍历整个链表，获得整个链表的长度，然后再找到倒数第 n 个节点。
找到了这个点之后，我们就可以定位到它的上一个位置。
对于链表节点的删除，设p节点为待删除节点，那么我们只需要获得p的上一个节点，然后把这个节点的下一个节点指向p.next 即可。
图示流程如下：
所以本题就是很纯粹的模拟。
ava
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
int siz = 0;
ListNode realhead = new ListNode(0,head);
ListNode pos = head;
while(pos != null){
siz++;
pos = pos.next;
}
pos = realhead;
for(int i = 1;i < siz - n + 1;i++)
pos = pos.next;
pos.next = pos.next.next;
return realhead.next;
}
}
效率也非常不错。
这道题目最后有一个小小的要求，问我们能不能“尝试使用一趟扫描实现？”
实际上一趟扫描是不太可能的，Leetcode官方给出的双下标的解法其实并不是一趟扫描，它利用了两个下标，第一个下标比第二个下标更靠前n个位置，这样子就可以通过所谓的一趟扫描解决，但是实际上，观察上述过程，两个下标加起来的移动次数还是没有变化，只是相当于将我们求长度以及寻找倒数第n 个点的两个循环写到了一起，实际的运行效率并没有提高，运算次数仍然一样。
总结
链表是除了数组之外，我们接触到的另外一个数据结构，对于它的增删改查，我们必须得了如指掌，因为它们是计算机用来存储数据单元的最基本的容器，即便计算机的学习是一个自顶向下的过程，但在掌握了顶层之后，我们应该一点点深挖下去，才能百尺竿头更进一步。
力扣链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
## 019.删除链表的倒数第 N 个节点
题意
给你一个链表，删除链表的倒数第 n 个节点，并且返回链表的头节点。
难度
中等
示例
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
分析
题意很清楚，就是要我们删除对应的节点，首先需要找到这个节点，我们可以遍历整个链表，获得整个链表的长度，然后再找到倒数第 n 个节点。
找到了这个点之后，我们就可以定位到它的上一个位置。
对于链表节点的删除，设p节点为待删除节点，那么我们只需要获得p的上一个节点，然后把这个节点的下一个节点指向p.next 即可。
图示流程如下：
所以本题就是很纯粹的模拟。
ava
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
int siz = 0;
ListNode realhead = new ListNode(0,head);
ListNode pos = head;
while(pos != null){
siz++;
pos = pos.next;
}
pos = realhead;
for(int i = 1;i < siz - n + 1;i++)
pos = pos.next;
pos.next = pos.next.next;
return realhead.next;
}
}
效率也非常不错。
这道题目最后有一个小小的要求，问我们能不能“尝试使用一趟扫描实现？”
实际上一趟扫描是不太可能的，Leetcode官方给出的双下标的解法其实并不是一趟扫描，它利用了两个下标，第一个下标比第二个下标更靠前n个位置，这样子就可以通过所谓的一趟扫描解决，但是实际上，观察上述过程，两个下标加起来的移动次数还是没有变化，只是相当于将我们求长度以及寻找倒数第n 个点的两个循环写到了一起，实际的运行效率并没有提高，运算次数仍然一样。
总结
链表是除了数组之外，我们接触到的另外一个数据结构，对于它的增删改查，我们必须得了如指掌，因为它们是计算机用来存储数据单元的最基本的容器，即便计算机的学习是一个自顶向下的过程，但在掌握了顶层之后，我们应该一点点深挖下去，才能百尺竿头更进一步。
力扣链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
知识星球
扫码加入星球
查看更多优质内容
https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412