代码随想录-DAY③-链表——leetcode 203 | 707 | 206

203

思路

设置一个虚拟头结点,这样所有节点就都可以按照统一的方式进行移除。
如果下一个节点的值等于 val,让节点 next 指针直接指向下下一个节点。
不要忘记清理节点内存。

时间复杂度: O(n)
空间复杂度: O(1)

代码
/**
 * 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* removeElements(ListNode* head, int val) {
        ListNode* dumphead = new ListNode(0, head);
        ListNode* pre = dumphead;

        while(pre->next != nullptr){
            if(pre->next->val == val){
                ListNode* tmp = pre->next;
                pre->next = pre->next->next;
                delete tmp;
            }
            else{
                pre = pre->next;
            }
        }
        head = dumphead->next;
        delete dumphead;
        return head;
    }
};

707

思路

addAtHead(val) 和 addAtTail(val) 可以借助 addAtIndex(index, val) 来实现
根据题意,优先判断 index 的有效性
使用虚拟头结点和变量size记录节点数

时间复杂度:get O(index),addAtHead O(1),addAtTail O(n),addAtIndex O(index),deleteAtIndex O(index)
空间复杂度:单函数 O(1),总体 O(n)

代码
class MyLinkedList {
public:
    MyLinkedList() {
        dummyhead = new ListNode(0);
        size = 0;
    }
    
    int get(int index) {
        ListNode* getnode = dummyhead;
        if(index<0 || index>=size){
            return -1;
        }
        for(int i=0; i<=index; i++){
            getnode = getnode->next;
        }
        return getnode->val;
    }
    
    void addAtHead(int val) {
        return addAtIndex(0, val);
    }
    
    void addAtTail(int val) {
        return addAtIndex(size, val);
    }
    
    void addAtIndex(int index, int val) {
        ListNode* node = dummyhead;
        if(index>size){
            return;
        }
        index = max(0,index);
        for(int i=0; i<index; i++){
            node = node->next;
        }
        ListNode* newnode = new ListNode(val);
        newnode->next = node->next;
        node->next = newnode;
        size++;
    }
    
    void deleteAtIndex(int index) {
        ListNode* node = dummyhead;
        if(index<0 || index>=size){
            return;
        }
        for(int i=0; i<index; i++){
            node = node->next;
        }
        ListNode* tmp = node->next;
        node->next = node->next->next;
        delete tmp;
        size--;
    }

private:
    ListNode* dummyhead;
    int size;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

206

思路

在遍历链表时,将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点,因此必须事先存储其前一个节点。在更改引用之前,还需要存储后一个节点。最后返回新的头引用。

时间复杂度: O(n)
空间复杂度: O(1)

代码
/**
 * 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* reverseList(ListNode* head) {
        ListNode *pre = nullptr, *cur = head, *temp;

        while(cur != nullptr){
            temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/781562.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Vben:表格的表头和表格的内容对不齐,以及解决方法

文章目录 一、问题描述二、解决方法 一、问题描述 基于Vue-Vbne-admin框架进行前端开发的时候&#xff0c;调用表格useTable函数实现表格之后&#xff0c;发现表格的表头和表格的内容对不齐。如下图所示。针对这种情况&#xff0c;本文记录了解决方法。 调用的模块如下&#x…

1958.力扣每日一题7/7 Java(100%解)

博客主页&#xff1a;音符犹如代码系列专栏&#xff1a;算法练习关注博主&#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出&#xff0c;及时修改感谢大家点赞&#x1f44d;收藏⭐评论✍ 目录 思路 解题方法 时间复杂度 空间复杂度 Code 思路 首先将指定位…

浏览器插件利器-allWebPluginV2.0.0.14-stable版发布

allWebPlugin简介 allWebPlugin中间件是一款为用户提供安全、可靠、便捷的浏览器插件服务的中间件产品&#xff0c;致力于将浏览器插件重新应用到所有浏览器。它将现有ActiveX插件直接嵌入浏览器&#xff0c;实现插件加载、界面显示、接口调用、事件回调等。支持谷歌、火狐等浏…

并查集(还有反集也在)

一.定义 定义&#xff1a; 并查集是一种树型的数据结构&#xff0c;用于处理一些不相交集合的合并及查询问题&#xff08;即所谓的并、查&#xff09;。比如说&#xff0c;我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等。 主要构成&#xff1a; 并查集…

2-27 基于matlab的一种混凝土骨料三维随机投放模型

基于matlab的一种混凝土骨料三维随机投放模型&#xff0c;为混凝土细观力学研究提供一种快捷的三维建模源代码。可设置骨料数量&#xff0c;边界距离、骨料大小等参数。程序已调通&#xff0c;可直接运行。 2-27 matlab 混凝土骨料三维随机投放模型 - 小红书 (xiaohongshu.com)…

Redis 7.x 系列【16】持久化机制之 AOF

有道无术&#xff0c;术尚可求&#xff0c;有术无道&#xff0c;止于术。 本系列Redis 版本 7.2.5 源码地址&#xff1a;https://gitee.com/pearl-organization/study-redis-demo 文章目录 1. 概述2. 执行原理2.1 Redis 6.x2.1.1 直接写2.1.2 重写 2.2 Redis 7.x2.2.1 直接写2…

PTA甲级1005:Spell It Right

错误代码&#xff1a; #include<iostream> #include<vector> #include<unordered_map> using namespace std;int main() {unordered_map<int, string> map {{0, "zero"}, {1, "one"}, {2, "two"}, {3, "three&qu…

线程安全的原因及解决方法

什么是线程安全问题 线程安全问题指的是在多线程编程环境中&#xff0c;由于多个线程共享数据或资源&#xff0c;并且这些线程对共享数据或资源的访问和操作没有正确地同步&#xff0c;导致数据的不一致、脏读、不可重复读、幻读等问题。线程安全问题的出现&#xff0c;通常是…

【大数据综合试验区1008】揭秘企业数字化转型:大数据试验区政策数据集大公开!

今天给大家分享的是国内顶级期刊中国工业经济2023年发布的最新期刊《政策赋能、数字生态与企业数字化转型——基于国家大数据综合试验区的准自然实验》文章中所使用到的数据集——国家大数据综合试验区政策数据集以及工具变量数据&#xff0c;该文章基于2009-2019年中国上市企业…

两个全开源的3D模型素材下载网站源码 3D图纸模型素材 三维图形素材会员下载站源码

今天推荐两个全开源的3D模型素材下载网站源码 3D图纸模型素材 三维图形素材会员下载站源码&#xff0c;这两个源码完整&#xff0c;都是基于thinkphp内核开发的&#xff0c;框架稳定&#xff0c;带数据库&#xff0c;源码文件&#xff0c;可以直接部署使用。 第一个&#xff1a…

【数据结构与算法】快速排序挖坑法

&#x1f493; 博客主页&#xff1a;倔强的石头的CSDN主页 &#x1f4dd;Gitee主页&#xff1a;倔强的石头的gitee主页 ⏩ 文章专栏&#xff1a;《数据结构与算法》 期待您的关注 ​

Redis源码整体结构

一 前言 Redis源码研究为什么先介绍整体结构呢?其实也很简单,作为程序员的,要想对一个项目有快速的认知,对项目整体目录结构有一个清晰认识,有助于我们更好的了解这个系统。 二 目录结构 Redis源码download到本地之后,对应结构如下: 从上面的截图可以看出,Redis源码一…

【密码学】信息安全五大属性

信息安全的五大属性&#xff0c;通常被称为CIA三元组加上两个额外的属性&#xff0c;他们是确保信息在存储、处理和传输过程中保持安全、完整和可用的关键要素。这些属性共同构成了信息安全的基础框架。 一、信息安全五大属性 我先给出一个直观的列表&#xff0c;方面大家后续…

BigDecimal(double)和BigDecimal(String)有什么区别?BigDecimal如何精确计数?

BigDecimal(double)和BigDecimal(String)的区别 double是不精确的&#xff0c;所以使用一个不精确的数字来创建BigDecimal&#xff0c;得到的数字也是不精确的。如0.1这个数字&#xff0c;double只能表示他的近似值。所以&#xff0c;当我们使用new BigDecimal(0.1)创建一个Bi…

69.WEB渗透测试-信息收集- WAF、框架组件识别(9)

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 内容参考于&#xff1a; 易锦网校会员专享课 上一个内容&#xff1a;68.WEB渗透测试-信息收集- WAF、框架组件识别&#xff08;8&#xff09; 有无waf存在&am…

前端必修技能:高手进阶核心知识分享 - CSS 阴影属性详解

CSS 涉及设计到阴影的相关内容包括三个方面&#xff1a;box-shadow属性&#xff08;盒子阴影&#xff09;、 text-shadow属性&#xff08;文本阴影&#xff09;、drop-shadow滤镜。 本篇文章旨在详细介绍和分析三种阴影的具体参数设置和典型用例。 box-shadow属性&#xff08;…

蚂蚁全媒体总编刘鑫炜谈新媒体时代艺术家如何创建及提升个人品牌

新媒体时代艺术家如何创建及提升个人品牌形象——专访蚂蚁全媒体总编刘鑫炜 图为蚂蚁全媒体总编刘鑫炜 在新媒体风潮席卷全球的今天&#xff0c;传统艺术与新媒体技术的融合越来越紧密。这种变革不仅改变了艺术作品的呈现方式&#xff0c;也给艺术家们提供了更多的可能性。那么…

从FasterTransformer源码解读开始了解大模型(2.1)代码通读03

从FasterTransformer源码解读开始了解大模型&#xff08;2.2&#xff09;代码解读03-forward函数 写在前面的话 本篇的内容继续解读forward函数&#xff0c;从650行开始进行解读 零、输出Context_embeddings和context_cum_log_probs的参数和逻辑 从653行开始&#xff0c;会…

怎样让家长单独查到自己孩子的期末成绩?

期末考试的钟声已经敲响&#xff0c;随着最后一份试卷的收卷&#xff0c;学生们的紧张情绪渐渐平息。然而&#xff0c;对于老师们来说&#xff0c;这仅仅是另一个忙碌周期的开始。成绩的统计、分析、反馈&#xff0c;每一项工作都不容小觑。尤其是将成绩单一一私信给家长&#…