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

2023-12-14 20:49:29

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;
    }
};

总结:

大家有没有发现其实法一和法二其实差不多,用栈的时候遍历一下就相当于长度的计算,快慢指针也很有意思,我觉得嗷~

总有些坑是要自己踩了才会影响深刻的,也会更加强大,所以,多多踩坑吧,宝子们~

祝你生活愉快~

刷题幸福哦~

文章来源:https://blog.csdn.net/qq_62649563/article/details/135000161
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。