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

链表入门(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题目)

来源&#xff1a;左程云算法 链表的题目我们经常是有思路但是实现起来总有些小问题&#xff0c;所以是准备笔试应多加练习的一类题 206. 反转链表 这道题我们可以新开链表来存&#xff0c;但是如果面试中有这道题&#xff0c;面试官让你优化又该如何呢&#xff1f;所以我们采…...

kibana开启访问登录认证

编辑es配置文件&#xff0c;添加以下内容开启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主要新特性如下&#xff1a; JEP 305&#xff1a;Pattern Matching for instanceof (Preview)instanceof 的模式匹配&#xff08;预览&#xff09; JEP 358&#xff1a;Helpful NullPointerExceptions 有用的 NullPointerExceptions…...

流量特征随机ua修改

作为一个蓝队吗喽&#xff0c;总是能看见因为ua头特征而直接被拦截的ip,当然了还有些是通过X-Forwarded-For被拦截的(X-Forwarded-For:fofa.info&#xff0c;不拦你才怪)&#xff0c; 主要是通过python的mitmproxy和fake_useragent两个模块进行实现&#xff0c;代码量极低 fr…...

CSP-S 2024 提高级 第一轮(初赛) 阅读程序(3)

【题目】 CSP-S 2024 提高级 第一轮&#xff08;初赛&#xff09; 阅读程序&#xff08;3&#xff09; 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 是一门系统级编程语言&#xff0c;以其卓越的性能、并发能力以及内存安全特性著称。Rust 由 Mozilla 推出&#xff0c;目标是在现代软件开发中提供一种安全高效的编程语言。其设计旨在提供安全、并发和高效的编程体验&#xff0c;同时保持开发效率和代码质量不…...

广东高校建设AIGC实验室时需要注意哪几个关键点?

随着人工智能技术的飞速发展&#xff0c;特别是生成式人工智能&#xff08;AIGC&#xff09;在各行各业中的广泛应用&#xff0c;它已经成为推动新一轮科技革命和产业变革的关键力量。教育部等相关部门近年来也高度重视人工智能领域的人才培养工作&#xff0c;强调要加快推动高…...

设计模式-PIMPL 模式

PIMPL&#xff08;Pointer to IMPLementation&#xff09;&#xff0c;又称Opaque Pointer模式或编译防火墙&#xff0c;是一种在C中广泛应用的编程技术。其核心思想是将类的实现细节从公共接口中分离出来&#xff0c;通过指向实现类的指针来访问类的具体功能。这种模式在提高代…...

Docker部署MongoDB教程

嘿&#xff0c;大家好&#xff01;今天我在三丰云免费服务器上进行了一次激动人心的MongoDB部署测试。这款免费云服务器1核CPU、1G内存、10G硬盘、5M带宽&#xff0c;是不错的免费服务器选择。 首先&#xff0c;让我们简要介绍一下使用到的Docker和MongoDB软件。Docker是一个开…...

堆排序易错点

1.建堆和调整堆&#xff08;插入和删除&#xff09; 建堆和调整堆的过程是不一样的&#xff1a; 建堆 从非终端节点编号的结点开始依次建立大根堆&#xff0c;例如: 拿第2个图说&#xff0c;首先比较-1&#xff0c;7&#xff0c;从中选一个小的&#xff0c;即“-1”&#xf…...

安卓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类组件生命周期整体情况 大致步骤&#xff1a; 什么是生命周期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”目录内&#xff0c;解压hadoop [csumaster0 ~]$ tar -zxvf ~/hadoop-2.6.0.tar.gz 解压成成功后自动在csu目录下创建hadoop-2.6.0子目录&#xff0c;可以用cd hadoo…...

一个自制的比较low的刷题软件

一个自制的比较low的刷题软件 一、背景 工作中往往涉及一些考试&#xff0c;比如阿里云ACP认证&#xff0c;华为GAUSS认证、软考等&#xff0c;应对这些考试的时候&#xff0c;我们往往是先看书后刷题&#xff08;当然也有直接刷题的大神&#xff0c;毕竟考试&#xff0c;懂的…...

【Java 集合】List接口 —— ArrayList 与 LinkedList 详解

List接口继承自Collection接口&#xff0c;是单列集合的一个重要分支。 在List集合中允许出现重复的元素&#xff0c;所有的元素是以一种线性方式进行存储的&#xff0c;在程序中可以通过索引&#xff08;类似于数组中的元素角标&#xff09;来访问集合中的指定元素。另外&…...

通信工程学习:什么是PNF物理网络功能

PNF:物理网络功能 PNF(Physical Network Function)即物理网络功能,是指支持网络功能的物理设备。以下是关于PNF的详细解释: 一、定义与特点 定义: PNF是网络设备厂商(如Cisco、华为、H3C等)通过专用硬件实体提供软件功能的设备。这些设备直接在物理服务器上运…...

Unity的Text组件中实现输入内容的渐变色效果

要在Unity的Text组件中实现输入内容的渐变色效果&#xff0c;默认的Text组件不直接支持渐变色。但是&#xff0c;你可以通过以下几种方式实现&#xff1a; ### 1. **使用Shader**来实现渐变效果 通过自定义Shader为Text组件创建一个渐变效果。这是一个常用的做法&#xff0…...

network-scripts目录下没有ens33文件的问题

作者&#xff1a;程序那点事儿 日期&#xff1a;2023/11/09 06:52 systemctl start NetworkManager #开启网络管理器nmcli con show #查看ens33网卡对应的是ifcfg-Wired_connection_3这个文件&#xff08;网络管理器要开启&#xff0c;不然报错&#xff09;&#xff0c;或者根据…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制

目录 节点的功能承载层&#xff08;GATT/Adv&#xff09;局限性&#xff1a; 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能&#xff0c;如 Configuration …...

CppCon 2015 学习:Time Programming Fundamentals

Civil Time 公历时间 特点&#xff1a; 共 6 个字段&#xff1a; Year&#xff08;年&#xff09;Month&#xff08;月&#xff09;Day&#xff08;日&#xff09;Hour&#xff08;小时&#xff09;Minute&#xff08;分钟&#xff09;Second&#xff08;秒&#xff09; 表示…...

2025年低延迟业务DDoS防护全攻略:高可用架构与实战方案

一、延迟敏感行业面临的DDoS攻击新挑战 2025年&#xff0c;金融交易、实时竞技游戏、工业物联网等低延迟业务成为DDoS攻击的首要目标。攻击呈现三大特征&#xff1a; AI驱动的自适应攻击&#xff1a;攻击流量模拟真实用户行为&#xff0c;差异率低至0.5%&#xff0c;传统规则引…...