链表入门(LeetCode题目)
来源:左程云算法
链表的题目我们经常是有思路但是实现起来总有些小问题,所以是准备笔试应多加练习的一类题
206. 反转链表
这道题我们可以新开链表来存,但是如果面试中有这道题,面试官让你优化又该如何呢?所以我们采用前后指针方法来解决
/*** 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;//前指针ListNode *next=nullptr;//后指针while(head){ next=head->next;//先把该节点的下一个结点存下来head->next=pre;//修改该结点的下一个结点为前一结点pre=head;//前一结点移到当前位置head=next;//当前结点往后移动}return pre;//最后pre保存新的头结点,另两个结点为空}
};
同时,本题还有递归解法,非常巧妙
/*** 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) {if(head==nullptr||head->next==nullptr)return head;//第一个条件只是判断初始链表为空的情况ListNode *cur=reverseList(head->next);//以[1,2,3,4,5]为例,现在head指向4,cur指向5head->next->next=head;//head->next指向反转链表的最后一个,此句把自己接到后面head->next=nullptr;//接到的是尾部,所以next为nullptrreturn cur;}
};
附录:反转双链表
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* pre = nullptr;ListNode* next = nullptr;while (head ) {next = head->next;head->next = pre;head->last = next;pre = head;head = next;}return pre;}
21. 合并两个有序链表
这里我们使用一个哨兵结点方便后续书写
/*** 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* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode head{};//哨兵结点ListNode* cur=&head;//指向哨兵结点while(list1&&list2){if(list1->val<list2->val){cur->next=list1;//指向小的list1=list1->next;//链表指针移动}else{cur->next=list2;list2=list2->next;}cur=cur->next;//合并链表指针移动到尾结点}cur->next=list1?list1:list2;//哪个有剩余就加上return head.next;//返回头节点}
};
2. 两数相加
这道题依然使用哨兵结点,便于处理
/*** 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* addTwoNumbers(ListNode* l1, ListNode* l2) {int up = 0;//算进位和余数ListNode* head = new ListNode;//哨兵结点ListNode* cur = head;//指针指向哨兵结点while (l1 || l2 || up) {//只要链表没遍历完,或进位里仍有数int val1 = l1 ? l1->val : 0;//链表不为空取值int val2 = l2 ? l2->val : 0;up += val1 + val2;//之前进上的位与当前相加ListNode* t = new ListNode(up % 10);//新建结点存答案up /= 10;//应进位多少cur->next = t;//接到答案链表后面cur = cur->next;//链表指针移动if (l1)l1 = l1->next; //链表不为空移动if (l2)l2 = l2->next;}return head->next;//返回哨兵结点保存的头结点}
};
86. 分隔链表
这个题如果我们扫描然后把小的放前面用到的指针比较多,较麻烦。
所以我们用两个链表分别存储,再最后合并即可。
/*** 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* partition(ListNode* head, int x) {//开两个链表分别存储,最后合并链表即可ListNode* lower = new ListNode(0);//<x的结点ListNode* upper = new ListNode(0);//>=x的结点//两个都是哨兵结点ListNode *p1 = lower, *p2 = upper;//指针分别指向两链表,便于后续增加结点if (!head)return head;//为空直接返回while (head) {//一直遍历if (head->val < x) {//小于接到lower链表p1->next = head;p1 = p1->next;head = head->next;} else {p2->next = head;//大于等于接到upper链表p2 = p2->next;head = head->next;}}p1->next = upper->next;//upper接到lower后面p2->next = nullptr;//尾部置nullreturn lower->next;}
};
相关文章:
链表入门(LeetCode题目)
来源:左程云算法 链表的题目我们经常是有思路但是实现起来总有些小问题,所以是准备笔试应多加练习的一类题 206. 反转链表 这道题我们可以新开链表来存,但是如果面试中有这道题,面试官让你优化又该如何呢?所以我们采…...
kibana开启访问登录认证
编辑es配置文件,添加以下内容开启es认证 vim /etc/elasticsearch/elasticsearch.yml http.cors.enabled: true http.cors.allow-origin: "*" http.cors.allow-headers: Authorization xpack.security.enabled: true xpack.security.transport.ssl.enable…...
Java 14Java 15新特性概述
一、Java 14 发布于2020年3月17日。Java 14主要新特性如下: JEP 305:Pattern Matching for instanceof (Preview)instanceof 的模式匹配(预览) JEP 358:Helpful NullPointerExceptions 有用的 NullPointerExceptions…...
流量特征随机ua修改
作为一个蓝队吗喽,总是能看见因为ua头特征而直接被拦截的ip,当然了还有些是通过X-Forwarded-For被拦截的(X-Forwarded-For:fofa.info,不拦你才怪), 主要是通过python的mitmproxy和fake_useragent两个模块进行实现,代码量极低 fr…...
CSP-S 2024 提高级 第一轮(初赛) 阅读程序(3)
【题目】 CSP-S 2024 提高级 第一轮(初赛) 阅读程序(3) 1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 const int maxn 1000000 5; 7 const int P1 998…...
如何在 Rust 中通过 Rumqttc 实现 MQTT 通信
Rust 简介 Rust 是一门系统级编程语言,以其卓越的性能、并发能力以及内存安全特性著称。Rust 由 Mozilla 推出,目标是在现代软件开发中提供一种安全高效的编程语言。其设计旨在提供安全、并发和高效的编程体验,同时保持开发效率和代码质量不…...
广东高校建设AIGC实验室时需要注意哪几个关键点?
随着人工智能技术的飞速发展,特别是生成式人工智能(AIGC)在各行各业中的广泛应用,它已经成为推动新一轮科技革命和产业变革的关键力量。教育部等相关部门近年来也高度重视人工智能领域的人才培养工作,强调要加快推动高…...
设计模式-PIMPL 模式
PIMPL(Pointer to IMPLementation),又称Opaque Pointer模式或编译防火墙,是一种在C中广泛应用的编程技术。其核心思想是将类的实现细节从公共接口中分离出来,通过指向实现类的指针来访问类的具体功能。这种模式在提高代…...
Docker部署MongoDB教程
嘿,大家好!今天我在三丰云免费服务器上进行了一次激动人心的MongoDB部署测试。这款免费云服务器1核CPU、1G内存、10G硬盘、5M带宽,是不错的免费服务器选择。 首先,让我们简要介绍一下使用到的Docker和MongoDB软件。Docker是一个开…...
堆排序易错点
1.建堆和调整堆(插入和删除) 建堆和调整堆的过程是不一样的: 建堆 从非终端节点编号的结点开始依次建立大根堆,例如: 拿第2个图说,首先比较-1,7,从中选一个小的,即“-1”…...
安卓13长按电源按键直接关机 andriod13不显示关机对话框直接关机
总纲 android13 rom 开发总纲说明 文章目录 1.前言2.问题分析3.代码分析4.代码修改5.编译6.彩蛋1.前言 有些设备需要在长按电源键的时候,直接关机。不需要弹出对话框进行询问。 2.问题分析 过滤电源按键,需要在系统里面处理的话,那么我们需要熟悉android的事件分发,然后再…...
React学习笔记(四)——React 组件生命周期
目录 1. 生命周期-概览 2. 生命周期-挂载阶段 3. 生命周期-更新阶段 4. 生命周期-卸载阶段 5. setState扩展-发现问题 6. setState扩展-更多用法 7. setState扩展-异步 1. 生命周期-概览 了解react类组件生命周期整体情况 大致步骤: 什么是生命周期React类组…...
PHP的guzzlehttp/guzzle库在碰到各种异常时的场景
PHP的guzzlehttp/guzzle库在碰到各种异常时的场景 结论: 经过测试得知 在http状态码为1xx, 2xx, 3xx时, 会在111处输出返回 在http状态码为4xx, 5xx时, 会在222处被捕获 在目标服务不可达或其他异常时会在333处被捕获 测试过程: 用其他程序写个接口, 实现输入什么状态码就返…...
多机部署,负载均衡-LoadBalance
文章目录 多机部署,负载均衡-LoadBalance1. 开启多个服务2. 什么是负载均衡负载均衡的实现客户端负载均衡 3. Spring Cloud LoadBalance快速上手使用Spring Cloud LoadBalance实现负载均衡修改IP,端口号为服务名称启动多个服务 负载均衡策略自定义负载均衡策略 LoadBalance原理…...
Hadoop安装与配置
一、Hadoop安装与配置 1、解压Hadoop安装包 找到hadoop-2.6.0.tar.gz,将其复到master0节点的”/home/csu”目录内,解压hadoop [csumaster0 ~]$ tar -zxvf ~/hadoop-2.6.0.tar.gz 解压成成功后自动在csu目录下创建hadoop-2.6.0子目录,可以用cd hadoo…...
一个自制的比较low的刷题软件
一个自制的比较low的刷题软件 一、背景 工作中往往涉及一些考试,比如阿里云ACP认证,华为GAUSS认证、软考等,应对这些考试的时候,我们往往是先看书后刷题(当然也有直接刷题的大神,毕竟考试,懂的…...
【Java 集合】List接口 —— ArrayList 与 LinkedList 详解
List接口继承自Collection接口,是单列集合的一个重要分支。 在List集合中允许出现重复的元素,所有的元素是以一种线性方式进行存储的,在程序中可以通过索引(类似于数组中的元素角标)来访问集合中的指定元素。另外&…...
通信工程学习:什么是PNF物理网络功能
PNF:物理网络功能 PNF(Physical Network Function)即物理网络功能,是指支持网络功能的物理设备。以下是关于PNF的详细解释: 一、定义与特点 定义: PNF是网络设备厂商(如Cisco、华为、H3C等)通过专用硬件实体提供软件功能的设备。这些设备直接在物理服务器上运…...
Unity的Text组件中实现输入内容的渐变色效果
要在Unity的Text组件中实现输入内容的渐变色效果,默认的Text组件不直接支持渐变色。但是,你可以通过以下几种方式实现: ### 1. **使用Shader**来实现渐变效果 通过自定义Shader为Text组件创建一个渐变效果。这是一个常用的做法࿰…...
network-scripts目录下没有ens33文件的问题
作者:程序那点事儿 日期:2023/11/09 06:52 systemctl start NetworkManager #开启网络管理器nmcli con show #查看ens33网卡对应的是ifcfg-Wired_connection_3这个文件(网络管理器要开启,不然报错),或者根据…...
Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...
2.Vue编写一个app
1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
深度学习习题2
1.如果增加神经网络的宽度,精确度会增加到一个特定阈值后,便开始降低。造成这一现象的可能原因是什么? A、即使增加卷积核的数量,只有少部分的核会被用作预测 B、当卷积核数量增加时,神经网络的预测能力会降低 C、当卷…...
面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践
作者:吴岐诗,杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言:融合数据湖与数仓的创新之路 在数字金融时代,数据已成为金融机构的核心竞争力。杭银消费金…...
