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

【力扣】19. 删除链表的倒数第 N 个结点

news 来源：原创 2024/5/9 13:46:28

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

相比于昨天，感觉刷题越来越轻松了~ 我进步了！

以后刷题力度要加快了，因为我报了蓝桥杯！加油~

法一：计算链表长度

思路：

首先用个函数来计算出该链表的长度，然后因为这里题目给的n是从后开始往前数的，所以我们需要计算出待删除结点的前一个结点的下标长度，然后这里我们引用了一个哑结点，主要是记录头部结点的位置。删除的原理就是让前一个结点->next指向其下一个结点，实现删除的目的。

cur->next=cur->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 length=0;while(head){++length;head=head->next;}return length;}//2.移除操作ListNode* removeNthFromEnd(ListNode* head, int n) {//创建一个结点为0且next指向head的指针ListNode* dumy=new ListNode(0,head);int length=getLength(head);ListNode* cur=dumy;for(int i=1;i<length-n+1;i++){cur=cur->next;}cur->next=cur->next->next;ListNode* ans=dumy->next;//释放空间，不要也行，不影响delete dumy;return ans;}
};

法二：栈

用栈的目的也是为了找出当前结点的前驱结点。然后就和上题一样了。

思路：

首先遍历链表让其进栈，然后push出栈n个，此时栈顶的元素既是n元素的前一个，然后进行操作即可。需要注意的是博主我在这里踩了个雷，那就是有头结点和没有设置头结点时报的错
然后在有头结点的情况下，是不需要考虑栈为空的情况的。比如说，当head=[1]，n=1时，此时头结点为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) {stack<ListNode*> stk;ListNode* cur=head;while(cur){stk.push(cur);cur=cur->next;}for(int i=1;i<=n;i++){stk.pop();}ListNode* pre;//若栈不为空if(!stk.empty()){pre=stk.top();}else{head=head->next;return head;}//用这种方法是没有考虑到头结点为空的情况的。细想一下，所以哑结点的作用就突出来了pre->next=pre->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*dumy=new ListNode(0,head);//2.控制两指针的距离ListNode* first=head;ListNode* second=dumy;//让first指针也就是张三先走n步for(int i=1;i<=n;i++){first=first->next;}//同时张三和李四以相同的速度行走直到张三到达终点while(first){first=first->next;second=second->next;}//让李四跳起来，远离炸弹second->next=second->next->next;return dumy->next;}
};