删除链表的倒数第 N 个结点
2023-02-18 16:36:38 时间
删除链表的倒数第 N 个结点
作者:Grey
原文地址:
题目描述
思路
由于题目要求: Could you do this in one pass?
所以这题的难点在于:
- 我们不通过获取链表长度的方式来拿需要删除的节点。
要定位到需要删除的点,我们可以这样操作,假设我们要删除的点是X,会有如下关系
其中:
-
X'点是X关于中点的对称点
-
Y是X前一个点
-
Y'是X’后一个点
所以,可以很容易的得到一个结论:
如果我设置两个指针,假设一个叫pre,一个叫cur,
-
cur从头开始走,当cur走到Y'位置的时候(即走了n+1步),pre开始从头走;
-
接下来cur和pre都继续向下一个位置移动,当cur移动到结尾(cur == null)的时候,pre应该正好在Y位置;
-
pre.next = pre.next.next;
这样就把X位置给删除掉了。
这道题另外一个需要注意的点是:
- 需要被删除的节点如果不是头节点,那么返回的链表节点应该是头节点。
- 如果需要删除的节点正好是头节点,那么返回的节点应该是头节点的下一个节点。
所以,如果上述两个指针移动的第一步:
cur从头开始走,当cur走到Y'位置的时候(即走了n+1步),正好是cur == null的位置。那pre不用走了,头节点即为需要删除的节点。
直接返回 head.next即可。
完整代码:
public static ListNode removeNthFromEnd(ListNode head, int n) {
ListNode cur = head;
ListNode pre = null;
while (cur != null) {
n--;
if (n == -1) {
pre = head;
}
if (n < -1) {
pre = pre.next;
}
cur = cur.next;
}
if (pre == null) {
return head.next;
}
pre.next = pre.next.next;
return head;
}
更多
相关文章
- [linux]centos安装宝塔面板
- [linux] linux宝塔面板安装GOFLY开源客服
- [docker] win10 docker桌面版镜像源
- [docker]解决:docker桌面版报错error during connect: This error may indicate that the docker daemon is not running
- [正则]正则表达式里面的?: ?! ?= ?<=
- 三连冠!腾讯Angel PowerFL联队斩获iDASH-2022隐私计算大赛同态加密赛道冠军
- 宝塔面板12.7(或更早)高危漏洞
- 在web页面中水晶报表显示速度过慢的原因
- 10年经验总结,华为fellow教你如何成为一名优秀的架构师?
- CANN5.0黑科技解密 | 高并发图片视频处理,为出行保驾,为生活添彩!
- 为啥你写的代码老有大串的if/else?
- 全链路数据血缘在满帮的实践
- 解析云原生2.0架构设计的8大关键趋势
- 万字详解什么是生成对抗网络GAN
- 基于MRS-Hudi构建数据湖的典型应用场景介绍
- 华为云首席架构师顾炯炯:敢为人先,探索架构创新之路如何走
- TCP的慢启动、拥塞避免、重传、快恢复乱七八糟总是记不清?11个连环问让你一次性打通任督二脉
- 计划会议想开好,这两件事必须清楚
- 漏洞检测方法如何选?详解源代码与二进制SCA检测原理
- 视镜:华为云媒体质量管理最新实践