当前位置: 首页 > news >正文

19. 删除链表的倒数第 N 个结点

19. 删除链表的倒数第 N 个结点

快慢指针

思路
快指针先走N步,然后快慢指针以相同速度向右遍历链表,当快指针指向最后一个结点时,慢指针指向倒数第N个结点的前驱结点。

补充
涉及到链表的插入与删除操作增加一个虚拟头结点准没错!

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(-1); // 虚拟头结点dummy.next = head;ListNode fast = dummy; // 快指针ListNode slow = dummy; // 慢指针// 快指针先走n步while (n != 0) {fast = fast.next;n--;}// 快指针指向最后一个结点时,慢指针指向倒数第N个结点的前驱结点while (fast.next != null) {fast = fast.next;slow = slow.next;}// 删除结点slow.next = slow.next.next;return dummy.next;}
}

递归

专门想了一下能否用递归,没想出来😿
递归思路模版
专注于当前层递归,思考下面3个问题:

  • 1、找整个递归的终止条件:递归应该在什么时候结束?
  • 2、找返回值:应该给上一级返回什么信息?
  • 3、本级递归应该做什么:在这一级递归中,应该完成什么任务?

1:p = null 时,表明当前递归的结点 p 指向链表末尾(尾结点后面),返回当前结点 p 的深度 depth = 0;
2:向上一层返回当前层结点的深度;
3:递归调用函数处理下一个结点开头的子链表,并接收下一层递归调用的返回值 depth 。若 depth = n,表明下一层调用的结点深度是 n (即倒数第 n 个结点),执行删除操作。

暂未解决
哑结点的作用是什么?
应该与虚拟结点作用相同:删除的可能是头结点,通过添加哑结点,使头结点与其他结点的删除操作相同。

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {// 创建哑结点,并连到原链表ListNode s = new ListNode(-1, head);// 递归调用remove(),从哑结点开始进行删除操作remove(s, n);// 返回新链表的头(去掉可能的哑结点)return s.next;}// 删除链表p的倒数第 n 个结点,并返回结点 p 的深度 depth(链表 p 的结点数量,即结点 p 在原链表中是倒数第 depth 个结点)public int remove(ListNode p, int n) {// 递归出口:当 p 为空时,表示 p 指向尾结点的后面,返回0if (p == null) return 0;// 递归体int depth = remove(p.next, n);if (depth == n) { // 若下一层调用的结点是倒数第 n 个结点,则删除p.next = p.next.next;}// 当前层传递给上一层的递归调用的信息return depth + 1; }
}
http://www.hskmm.com/?act=detail&tid=33288

相关文章:

  • Day13
  • 第一章日志分析-mysql应急响
  • 操作系统应用构建(十二)RustDesk 用户服务器搭建——东方仙盟筑基期
  • python-IDLE定制界面大小
  • 高级语言程序设计第1次作业
  • Maui:通过附加属性将命令绑定到事件
  • 超好用的浏览器多开小工具!轻松管理多个账号,可以无限制使用其他插件
  • 微服务组件-Eureka 科技详解
  • 新学期每日总结(第10天)
  • List.subList() 返回值为什么不能强转成 ArrayList
  • 奶奶都能看懂的 C++ —— 手把手指针
  • 10/17
  • CSP-2024 T4
  • 02-类与对象课后作业
  • NOIP2021 T2
  • 从零开始实现简易版Netty(九) MyNetty 实现池化内存的线程本地缓存
  • 杏帘招客饮,在望有山庄。
  • 洛谷 P8512
  • 从libtorch_cuda.so中提取某个函数的sass汇编指令
  • 【题解】成外友谊赛
  • 小程序商城客服系统
  • ubuntu 主机创建虚拟 ip,应对容器内部配置了宿主固定 ip,宿主迁移网络环境后容器报错
  • 2025权威报告:微信编辑器排版Top 10工具推荐(全链路解决方案)
  • 洛谷 P10149
  • 从0到1构建企业数据资产 - 智慧园区
  • 2025.10.17
  • 一行代码清空所有 docker 容器的日志文件
  • 塔吊施工 “隐形风险” 克星!思通数科 AI 卫士精准识别核心部件隐患
  • ubuntu配置vsftpd
  • 时序数据库 Apache IoTDB 等你“打卡”!2025 OSCAR 开源产业大会完整版议程揭晓