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

力扣题目解析--删除链表的倒数第n个节点

题目

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

示例 1:

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

示例 2:

输入:head = [1], n = 1
输出:[]

示例 3:

输入:head = [1,2], n = 1
输出:[1]

提示:

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

代码展示

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode *dummy=new ListNode(0);dummy->next=head;ListNode *current=dummy;ListNode *fast=dummy;ListNode *slow=dummy;for(int i=0;i<n;i++){if(fast->next==nullptr){delete dummy;return head;}fast=fast->next;}while (fast->next!=nullptr){fast=fast->next;slow=slow->next;}ListNode* toDelete =slow->next;slow->next=slow->next->next;delete toDelete;ListNode* newHead=dummy->next;delete dummy;return newHead;}
};

写者心得

要想搞明白这个题就必须得先看得懂题目在开头给的注释,那里面有关于对于列表是怎么设置的,写者就是在先去搞明白他是怎样设置列表之后再写代码的。这结构体设置的并不难,但其中有一个点是我搞错了的,val它其实是链表中的值,而我一直把它当做链表的一个元素来看待,所以造成了一些错误。代码有一些写的比较好的地方:

1.虚拟头节点

对比分析

  1. 删除头节点

    • 没有虚拟头节点:需要单独处理头节点的删除情况,代码复杂度增加。
    • 有虚拟头节点:删除头节点和其他节点的操作一致,代码简洁。
  2. 代码简洁性

    • 没有虚拟头节点:需要更多的条件判断,代码冗长。
    • 有虚拟头节点:代码结构更清晰,易于理解和维护。

虚拟头节点在链表中是非常常用的,其实它的作用很简单,就是当你在处理列表中节点的时候,有可能会处理到头节点的情况,正是因为我们把这个头节点虚拟化了,所以就不需要考虑这个问题了,这样子可以省去我们许多关于头节点的条件设置

2.双指针

但其实这个双指针和我们在前面所用到的双指针是完全不同的两个东西,过去的双指针是为了遍历数组 ,而这个双指针则是为了寻找节点,其实这个思路很像是双循环,一个负责遍历,另一个则负责删除,所以一个指针设为快指针,另一个指针设为慢指针,这样就可以在链表之中寻找节点,我想这个方法应该和双循环暴力破解有异曲同工之处,而在接下来我们处理链表问题的时候,会经常用到这样子的思路和这样的做法。

代码解析

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/

这部分定义了一个单链表节点的结构体 ListNode,包含三个构造函数:

  • 默认构造函数:ListNode() : val(0), next(nullptr) {}
  • 带一个参数的构造函数:ListNode(int x) : val(x), next(nullptr) {}
  • 带两个参数的构造函数:ListNode(int x, ListNode *next) : val(x), next(next) {}

创建虚拟头节点

        ListNode *dummy = new ListNode(0);dummy->next = head;
  • 创建一个虚拟头节点 dummy,其值为 0next 指向原链表的头节点 head
  • 虚拟头节点的作用是简化边界条件的处理,特别是删除头节点的情况。

初始化指针

        ListNode *current = dummy;ListNode *fast = dummy;ListNode *slow = dummy;
  • 初始化三个指针 currentfast 和 slow,都指向虚拟头节点 dummy

快指针先走 n 步

        for (int i = 0; i < n; i++) {if (fast->next == nullptr) {delete dummy;return head;}fast = fast->next;}
  • 使用一个 for 循环让快指针 fast 先向前移动 nn 步。
  • 在每次移动前,检查 fast->next 是否为 nullptr,如果是,说明链表长度小于 nn,直接返回原链表。
  • 如果链表长度大于等于 nn,继续移动快指针。

同步移动快指针和慢指针

        while (fast->next != nullptr) {fast = fast->next;slow = slow->next;}
  • 使用一个 while 循环同步移动快指针 fast 和慢指针 slow,直到快指针到达链表的末尾。
  • 当快指针到达链表末尾时,慢指针正好指向倒数第 nn 个节点的前一个节点。

删除慢指针的下一个节点

        ListNode* toDelete = slow->next;slow->next = slow->next->next;delete toDelete;
  • 记录要删除的节点 toDelete,即 slow->next
  • 将慢指针的 next 指针指向要删除节点的下一个节点,从而跳过要删除的节点。
  • 释放要删除节点的内存。

返回新的头节点

        ListNode* newHead = dummy->next;delete dummy;return newHead;}
};
  • 返回新的头节点 newHead,即 dummy->next
  • 释放虚拟头节点的内存。
  • 返回新的头节点。

总结

通过使用虚拟头节点和双指针法,我们可以有效地删除链表中的倒数第 nn 个节点。虚拟头节点简化了边界条件的处理,双指针法确保了我们能够准确地找到要删除的节点的位置。

 

http://www.lryc.cn/news/481445.html

相关文章:

  • Knowledge Graph-Enhanced Large Language Models via Path Selection
  • Android 项目模型配置管理
  • 「QT」几何数据类 之 QSizeF 浮点型尺寸类
  • Essential Cell Biology--Fifth Edition--Chapter one(2)
  • 大语言模型LLMs在医学领域的最新进展总结
  • 云防护单节点2T抗攻击能力意味着什么?
  • IDEA在编译时: java: 找不到符号符号: 变量 log
  • HTML 基础架构:理解网页的骨架
  • FPGA学习笔记#5 Vitis HLS For循环的优化(1)
  • web实操4——servlet体系结构
  • Linux开发讲课48--- Linux 文件系统概览
  • Node.js 模块详解
  • 大厂面试真题-说说tomcat的优缺点
  • Linux系统编译boot后发现编译时间与Windows系统不一致的解决方案
  • WPS Office手机去广高级版
  • Python爬虫基础-正则表达式!
  • Python处理PDF组件使用及注意事项
  • langgraph_plan_and_execute
  • [代码随想录打卡Day8] 344.反转字符串 541. 反转字符串II 54. 替换数字
  • DCN DCWS-6028神州数码 AC 设备配置笔记
  • Go语言的常用内置函数
  • 华为OD技术一面手撕题
  • Qt低版本多网卡组播bug
  • Leetcode:540. 有序数组中的单一元素
  • Python数据分析NumPy和pandas(二十七、数据可视化 matplotlib API 入门)
  • 数组指针和指针的区别
  • Linux git-bash配置
  • 【后端速成Vue】computed计算属性
  • 力扣-每日温度
  • (Go语言)初上手Go?本篇文章帮拿捏Go的数据类型!