程序地带

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


在这里插入图片描述 链表=双指针=空间鲁棒性 快指针先走n步,当快指针走到null时,慢指针指向倒数第n个。因为遍历一遍,所以用一个int变量记录快指针走了几步,当快指针走的步数大于等于n时,才让慢指针开始走。因为要删除,所以要来一个pre指针记录当前指针的前驱指针,删除操作就是直接让pre指向当前指针的next即可。最后判断,如果快指针在走n步直接走到结尾了,那么证明要删除头结点,直接返回head->next即可,通过判断pre是否为空来看是否是删除头。否则就删除slow指针指向的结点,最后返回head


/**
* 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) {
//给定n有效,就不用判断链表长度什么的了
//链表=双指针=空间鲁棒性
//先通过双指针找到第n个结点,然后将它的前后相连即可,快指针先走n步,慢指针才开始走,快走到尾了,慢就是第n个,在走的过程要时刻时刻记录当前指针的前一个指针方便删除当前指针,当快是null时,慢就是倒数第n个
if(head == nullptr || head->next == nullptr) return nullptr;
ListNode* pre = nullptr;
//head可能要变,因为可能删除的就是头
ListNode* slow = head, *fast = head;
int xianzou = 0;
while(fast != nullptr){
if(xianzou >= n){
pre = slow;
slow = slow->next;
}
fast = fast->next;
xianzou++;
}
//如果前驱指针没有改变,证明在快指针先走n步的时候直接走到链表尾了,证明要删除的就是头结点
if(pre == nullptr) return head->next;
pre->next = slow->next;
return head;
}
};

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/J_avaSmallWhite/article/details/112760918

随机推荐

python竞赛题解答_用python解NOIP 竞赛题

以下为2017年全国NOIP提高组复赛的第1题:怎么样,读完题是不是感觉特别懵。——我是谁,我在哪里?接下来我们来慢慢解析这道让人摸不着头脑的竞...

胡文燕 阅读(539)

十分钟学会CSS——篇二

十分钟学会CSS——篇二

文章目录前言一、font相关属性1.css的单位2.css中的颜色表示3.css文字属性4.css字体粗细二、text相关属性三、间距四、文本溢出五、行内元素垂直对齐前言网页的组成一共包括三部分&#x...

安生生爱做梦 阅读(854)

flink写入 mysql_通过实时计算 Flink 写入数据

创建数据写入任务为了方便介绍,本节的数据源采用随机数据源(random),实际使用中可以根据实际情况创建数据源。在实时计算控制台上,点击项目管理>项目列...

小杨叔聊生化环材 阅读(701)

USACO 1359. 城堡(并查集)

USACO 1359. 城堡(并查集)

文章目录1359.城堡AcWing网站原题通道1359.城堡题意分析:这道题难度并不大,只要熟练使用并查集即可。给我们一张地图,#代表墙壁,我们...

无敌少年小旋风 阅读(790)

ubuntu 安装vmware tools Linux常用命令(部分)

ubuntu 安装vmware tools Linux常用命令(部分)

ubuntu安装vmwaretools创建新的虚拟机到选择客户机操作系统选择如下图俩种系统版本:选择要将虚拟机放到的位置下一步选择自定义硬件使用ISO映像文件(ubuntu...

去哪? 阅读(272)

SQL——coalesce函数详解

coalesce的作用:(1)将控制替换成其他值;(2)返回第一个非空值coalesce函数:COALESCE是一个函数,(expression...

qq_45471034 阅读(262)

Triangle Numbers

题目链接:TriangleNumbers显然一个非0数字出现3次及以上,那么一定合法。否则每个数字出现次数为0,1,2然后状态压缩之后数位dp即...

青烟绕指柔! 阅读(823)

MyBatis 源码解读-typeAliasesElement()

接下来,我们解析<typeAliases>标签,我们在讲配置的时候也讲过,它有两种定义方式,一种是直接定义一个类的别名,...

Leon_Jinhai_Sun 阅读(579)