如何用代码做网站,牛客网官网,可以免费建网站的,导航网页19. 删除链表的倒数第 N 个结点
相比于昨天#xff0c;感觉刷题越来越轻松了~ 我进步了#xff01;
以后刷题力度要加快了#xff0c;因为我报了蓝桥杯#xff01;加油~ 法一#xff1a;计算链表长度
思路#xff1a;
首先用个函数来计算出该链表的长度#xff0c;然…19. 删除链表的倒数第 N 个结点
相比于昨天感觉刷题越来越轻松了~ 我进步了
以后刷题力度要加快了因为我报了蓝桥杯加油~ 法一计算链表长度
思路
首先用个函数来计算出该链表的长度然后因为这里题目给的n是从后开始往前数的所以我们需要计算出待删除结点的前一个结点的下标长度然后这里我们引用了一个哑结点主要是记录头部结点的位置。删除的原理就是让前一个结点-next指向其下一个结点实现删除的目的。
cur-nextcur-next-next;也就是这样
代码
/*** 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://1.链表长度int getLength(ListNode* head){int length0;while(head){length;headhead-next;}return length;}//2.移除操作ListNode* removeNthFromEnd(ListNode* head, int n) {//创建一个结点为0且next指向head的指针ListNode* dumynew ListNode(0,head);int lengthgetLength(head);ListNode* curdumy;for(int i1;ilength-n1;i){curcur-next;}cur-nextcur-next-next;ListNode* ansdumy-next;//释放空间不要也行不影响delete dumy;return ans;}
}; 法二栈
用栈的目的也是为了找出当前结点的前驱结点。然后就和上题一样了。
思路
首先遍历链表让其进栈然后push出栈n个此时栈顶的元素既是n元素的前一个然后进行操作即可。需要注意的是博主我在这里踩了个雷那就是有头结点和没有设置头结点时报的错然后在有头结点的情况下是不需要考虑栈为空的情况的。比如说当head[1]n1时此时头结点为0在栈中还没弹出的情况下stk[0,1]的弹出之后就是stk[0]此时stack.top()是不为空的也就是不会报空指针异常的操作的但是如果不需要头结点的话那就请判断一下最后我的代码是无结点的情况。
代码
/*** 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) {stackListNode* stk;ListNode* curhead;while(cur){stk.push(cur);curcur-next;}for(int i1;in;i){stk.pop();}ListNode* pre;//若栈不为空if(!stk.empty()){prestk.top();}else{headhead-next;return head;}//用这种方法是没有考虑到头结点为空的情况的。细想一下所以哑结点的作用就突出来了pre-nextpre-next-next;return head;}
};
法三快慢指针
题解
这个的原理就是有两个人比如说张三和李四。他俩在一条道上走起点相同但是张三会比李四先走n步二者行走速度始终相同直到张三走到终点那最后张三和李四的距离是不是n那我现在在这条道的倒数n的距离设置一个炸弹但是张三买了装备所以炸不死他。但是李四可以那结合刚刚说的是不是张三的终点就是李四的死亡想一下二者的距离是n,此时张三已经到了。那在这道题中我想要得到的是当张三到达终点时李四走到的隔炸弹一个单位的距离然后跳一步直接跳过炸弹。怎么操作呢只要在最开始的时候设置一个哑节点张三指向头结点李四指向哑节点同时哑结点距离头结点只有一个单位的距离就可以了吖~对吧
代码
/*** 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) {//1.设置哑结点ListNode*dumynew ListNode(0,head);//2.控制两指针的距离ListNode* firsthead;ListNode* seconddumy;//让first指针也就是张三先走n步for(int i1;in;i){firstfirst-next;}//同时张三和李四以相同的速度行走直到张三到达终点while(first){firstfirst-next;secondsecond-next;}//让李四跳起来远离炸弹second-nextsecond-next-next;return dumy-next;}
};
总结
大家有没有发现其实法一和法二其实差不多用栈的时候遍历一下就相当于长度的计算快慢指针也很有意思我觉得嗷~
总有些坑是要自己踩了才会影响深刻的也会更加强大所以多多踩坑吧宝子们~
祝你生活愉快~
刷题幸福哦~
