【算法】删除链表的倒数第 N 个结点
创始人
2024-12-29 12:04:33
0次

难度:中等

题目

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

示例:

示例1:
输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]

提示:
● 链表中结点的数目为 sz
● 1 <= sz <= 30
● 0 <= Node.val <= 100
● 1 <= n <= sz

解题思路:

解决这个问题,一个常见的策略是使用“快慢指针”技巧。这个方法的关键是先让一个指针(快指针)提前走n步,然后两个指针(快指针和慢指针)一起前进,当快指针到达链表尾部时,慢指针所在的位置就是要删除的节点的前一个位置。接下来,只需要做适当的指针调整就可以删除目标节点。

  1. 初始化两个指针:slow和fast,均指向链表头部。
  2. 快指针先走:让fast指针先向前移动n步。
  3. 同步前进:如果fast还没有到达链表尾部,那么slow和fast同时向前移动。
  4. 定位删除节点:当fast到达链表尾部时,slow所指向的节点就是待删除节点的前一个节点。
  5. 删除节点:调整指针,跳过待删除的节点。
  6. 特殊情况处理:如果要删除的是头节点,需要特殊处理。

JavaScript实现:

首先,定义链表节点结构(假设链表节点类已经定义好,包含val和next属性):

class ListNode {     constructor(val, next = null) {         this.val = val;         this.next = next;     } } 

接下来,实现删除倒数第n个节点的函数:

function removeNthFromEnd(head, n) {     // 创建一个哑节点作为辅助,防止删除头节点时的边界问题     let dummy = new ListNode(0);     dummy.next = head;          let slow = dummy;     let fast = dummy;          // 让fast先走n+1步,因为dummy的存在,所以fast走到n步时,slow恰好在正确的位置     for (let i = 0; i <= n; i++) {         fast = fast.next;     }          // 现在两个指针一起走,当fast走到链表尾部时,slow刚好在待删节点的前一个位置     while (fast !== null) {         slow = slow.next;         fast = fast.next;     }          // 删除slow.next指向的节点     slow.next = slow.next.next;          // 返回真正的头节点     return dummy.next; } 

这段代码首先通过哑节点避免了删除头节点时的边界问题,然后通过快慢指针技巧准确找到了待删除节点的前驱节点,并进行了节点的删除操作。最后返回更新后的链表头节点。

相关内容

热门资讯

研究成果开挂!红拐弯开挂多功能... 研究成果开挂!红拐弯开挂多功能AI教程,红拐弯原来有开挂教程红拐弯辅助器是一种具有地方特色的麻将游戏...
研究成果透视器!领悟棋牌透视器... 研究成果透视器!领悟棋牌透视器多功能AI教程,领悟棋牌一直真的有透视器教程1、下载好领悟棋牌正确养号...
揭秘真相辅助器!战皇辅助器多功... 揭秘真相辅助器!战皇辅助器多功能AI技巧,战皇一贯真的有辅助器技巧进入游戏-大厅左侧-新手福利-激活...
必看攻略辅助!红拐弯辅助多功能... 必看攻略辅助!红拐弯辅助多功能AI教程,红拐弯一贯真的有辅助教程1、每一步都需要思考,不同水平的挑战...
重大通报透视器!半岛透视器多功... 重大通报透视器!半岛透视器多功能AI工具,半岛竟然存在有透视器工具1)半岛免费钻石:进一步探索半岛免...
玩家必备教程开挂!富友茶苑开挂... 玩家必备教程开挂!富友茶苑开挂多功能AI脚本,富友茶苑竟然真的有开挂脚本富友茶苑破解侠是真的助透视。...
玩家必看科普辅助!冰球突破辅助... 玩家必看科普辅助!冰球突破辅助多功能AI插件,冰球突破总是有辅助插件1、上手简单,内置详细流程视频教...
一分钟揭秘外挂!皮皮衡阳字牌外... 一分钟揭秘外挂!皮皮衡阳字牌外挂多功能AI方法,皮皮衡阳字牌切实有外挂方法1、任何皮皮衡阳字牌透视是...
推荐攻略透视器!九九麻将透视器... 推荐攻略透视器!九九麻将透视器多功能AIapp,九九麻将原来是真的有透视器app1、九九麻将辅助软件...
一分钟了解开挂!鸿福休闲开挂多... 一分钟了解开挂!鸿福休闲开挂多功能AI教程,鸿福休闲原来存在有开挂教程1、鸿福休闲免费辅助多个强度级...