您现在的位置是:首页 > Javascript
当前栏目
每日:删除链表倒数第 N 个结点
2023-03-07 09:48:30 时间
本文转载自微信公众号「三分钟学前端」,作者sisterAn。转载本文请联系三分钟学前端公众号。
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
- 给定一个链表: 1->2->3->4->5, 和 n = 2.
- 当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。
进阶:
你能尝试使用一趟扫描实现吗?
解法:快慢指针
解题思路: 需要删除链表中的倒数第 n 个节点,我们需要知道的就是倒数第 n+1 个节点,然后删除删除倒数第 n+1 节点的后继节点即可
步骤:
使用 2 个指针:
- fast 快指针提前走 n+1 步
- slow 指针指向当前距离 fast 倒数第 n 个节点, 初始为 head
然后, fast 、 slow 同步向前走,直到 fast.next 为 null
此时,fast 为最后一个节点,slow 就是倒数第 n+1 个节点,此时问题就变更为删除链表中的 slow 的后继节点
但存在一个问题,当链表长度为 n 时,fast 是前进不到 n+1 个节点位置的,所以此时有两种解决思路:
- 创建一个头节点 preHead ,设置 preHead.next = head ,这样就可以解决以上问题,删除倒数第 n 个节点后,返回的 preHead.next 即可
- 另外一种是,fast 快指针提前走 n 步后,判断 fast.next 是否为 null ,即 fast 是否是最后一个节点,如果是,则 head 为倒数第 n 个节点,此时问题可以简化为删除头节点;如果不是, fast = fast.next ,fast 再前进一步,slow 为倒数第 n+1 个节点,也解决了以上问题。
解决方案一:添加 preHead 节点
- const removeNthFromEnd = function(head, n) {
- let preHead = new ListNode(0)
- preHead.next = head
- let fast = preHead, slow = preHead
- // 快先走 n+1 步
- while(n--) {
- fast = fast.next
- }
- // fast、slow 一起前进
- while(fast && fast.next) {
- fast = fast.next
- slow = slow.next
- }
- slow.next = slow.next.next
- return preHead.next
- };
解决方案二:单独处理倒数第 n 节点
- const removeNthFromEnd = function(head, n) {
- let fast = head, slow = head
- // 快先走 n 步
- while(--n) {
- fast = fast.next
- }
- if(!fast.next) return head.next
- fast = fast.next
- // fast、slow 一起前进
- while(fast && fast.next) {
- fast = fast.next
- slow = slow.next
- }
- slow.next = slow.next.next
- return head
- };
时间复杂度:O(n)
空间复杂度:O(1)
来源:https://github.com/sisterAn/JavaScript-Algorithms
相关文章
- 鲜为人知但很有用的 HTML 属性
- 翻转再翻转!有意思的水平横向溢出滚动
- 自定义计数器小技巧!CSS 实现长按点赞累加动画
- 过五关!React高频面试题指南
- 软件开发中的十个认知偏差
- 不需要 JS!仅用 CSS 也能达到监听页面滚动的效果!
- 一文读懂TypeScript类型兼容性
- Vue 的响应式原则与双向数据绑定
- 快速掌握 TypeScript 新语法:Infer Extends
- JWT教你如何证明你是我的人!
- 一篇带给你 V8 GC 的实现
- 面试官:请使用JS完成一个LRU缓存?
- 通过可视化来学习JavaScript事件循环
- 新的跨域策略:使用 COOP、COEP 为浏览器创建更安全的环境
- 为什么有人说 vite 快,有人却说 vite 慢?
- 种草 Vue3 中几个好玩的插件和配置
- 超全面的前端工程化配置指南
- Vue 状态管理未来样子
- Volatile关键字能保证原子性么?
- 面试突击:SpringBoot 有几种读取配置文件的方法?