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

链表学习之反转链表

链表解题技巧

  • 额外的数据结构(哈希表);
  • 快慢指针;
  • 虚拟头节点;

反转链表

分别实现单向链表和双向链表的反转。

要求:长度为N的链表,时间复杂度为O(N),额外空间复杂度为O(1)。

反转单向链表:

方法1(使用栈,时:O(N),空:O(N)):

  1. 第一次遍历将数据添加至栈中;
  2. 定义一个空节点,tmp记录,cur指向该节点;
  3. 栈不为空开始循环出栈:
    1. cur的next指向的栈顶元素;
    2. 栈顶元素出栈;
    3. cur移动到next的位置;
  4. cur现在在最后一个位置,将其next赋值为nullptr;
  5. cur指向tmp(空节点)的next位置,并删除tmp;
  6. 返回cur(新的头节点);
LinkedNode* LinkedList::reverseWithStack(LinkedNode *head) {if (head == nullptr || head->next == nullptr) {return head;}std::stack<LinkedNode*> stk;LinkedNode* cur = head;while (cur) {stk.push(cur);cur = cur->next;}LinkedNode* tmp = new LinkedNode();cur = tmp;while (!stk.empty()) {cur->next = stk.top();stk.pop();cur = cur->next;}cur->next = nullptr;cur = tmp->next;delete tmp;return cur;
}

方法2(双指针,时:O(N),空:O(1)):

双指针解法:

  1. 定义两个指针new_head,cur,初始new_head指向head,cur指向head的next;
  2. cur不为nullptr则开始循环:
    1. head的next赋值为cur的next;
    2. cur的next赋值为new_head;
    3. new_head移动到cur;
    4. cur移动到head的next;
  3. 最后返回new_head即可。
LinkedNode* LinkedList::reverse(LinkedNode *head) {if (head == nullptr || head->next == nullptr) {return head;}LinkedNode *new_head = head;LinkedNode *cur = head->next;while (cur) {head->next = cur->next;cur->next = new_head;new_head = cur;cur = head->next;}return new_head;
}

反转双链表

DoubleLinkedNode* LinkedList::reverseDoubleLinkedList(DoubleLinkedNode *head) {if (head == nullptr || head->next == nullptr) {return head;}DoubleLinkedNode *pre = head;DoubleLinkedNode *cur = head->next;while (cur) {DoubleLinkedNode *tmp = pre->next;pre->next = pre->pre;pre->pre = tmp;pre = cur;cur = cur->next;}return pre;
} 

相关文章:

链表学习之反转链表

链表解题技巧 额外的数据结构&#xff08;哈希表&#xff09;&#xff1b;快慢指针&#xff1b;虚拟头节点&#xff1b; 反转链表 分别实现单向链表和双向链表的反转。 要求&#xff1a;长度为N的链表&#xff0c;时间复杂度为O(N)&#xff0c;额外空间复杂度为O(1)。 反转…...

ONNXRUNTUIME实例分割网络说明

ONNXRUNTUIME c使用&#xff08;分割网络&#xff09;与相关资料&#xff08;暂记&#xff09; initiate a env with an id name(使用id名称启动env) create session (创建会话 ) onnxenv -> sessioninputname [“x”] ,outputname [“t”]inputnodedim [[1,1,192,192…...

几行代码,就写完懒加载啦?

Ⅰ、前言 「懒加载」是网页中非常 常见的&#xff1b;为了减少系统的压力&#xff0c;对于一些电商系统出场频率非常高&#xff1b;那么大家一般用什么方式去实现 「懒加载」 呢 &#xff1f; ① 通过 scroll 的形式&#xff1a; 通过 滚动「scroll」事件&#xff0c;然后去判…...

PyTorch常用的损失函数(ChatGPT)

L1Loss nn.L1Loss 也称为平均绝对误差&#xff08;Mean Absolute Error&#xff0c;MAE&#xff09;。它计算预测值与真实值之间的差异&#xff08;即误差&#xff09;&#xff0c;然后取绝对值并求和&#xff0c;最后除以样本数量得到平均误差。具体来说&#xff0c;对于一批…...

LeetCode——1237. 找出给定方程的正整数解

一、题目 来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 链接&#xff1a;https://leetcode.cn/problems/find-positive-integer-solution-for-a-given-equation/description/ 翻译一下题目 意思是&#xff0c;这是一个二维单调递增的函数&#xff0c;函数一共有 9 …...

系统编程中的进程的概念No.3【进程状态】

引言&#xff1a; 北京时间&#xff1a;2023/2/17/8:17&#xff0c;目前听着超能陆战队主题曲《Immortals》&#xff0c;感觉又要螺旋式升天&#xff0c;并且为我今天上午没课感到happy&#xff0c;所以继我们很久以前的关于进程的博客&#xff0c;今天我们就再来学习一下有关…...

推荐 3 款 Golang 语义化版本库

文章目录1.什么是语义化版本 2.0.02.Golang 语义化版本库比较3.小结参考文献1.什么是语义化版本 2.0.0 语义化版本 2.0.0&#xff08;Semantic Versioning 2.0.0&#xff09;是一种用于标识软件版本的约定和规范。它包含三个数字组成的版本号&#xff0c;格式为“MAJOR.MINOR.…...

Windows平台使用gdb连接qemu虚拟机上的系统

先安装MinGW&#xff1b; 除了gcc、g&#xff0c;把gdb也选上&#xff1b;可能选第一个就可以了&#xff0c;不清楚把后面几个也选上&#xff1b; 安装完成看一下gcc, g&#xff0c;gdb&#xff0c;编译工具和调试器都有了&#xff1b; 把bin目录加到环境变量&#xff1b; 看一…...

【博客624】MAC地址表、ARP表、路由表(RIB表)、转发表(FIB表)

MAC地址表、ARP表、路由表(RIB表/FIB表) MAC地址表 MAC地址表是交换机等网络设备记录MAC地址和端口的映射关系&#xff0c;代表了交换机从哪个端口学习到了某个MAC地址&#xff0c;交换机把这个信息记录下来&#xff0c;后续交换机需要转发数据的时候就可以根据报文的目的MAC地…...

【蓝桥日记⑤】2014第五届省赛(软件类)JavaA组❆答案解析

【蓝桥日记⑤】2014第五届省赛&#xff08;软件类&#xff09;JavaA组☃答案解析 文章目录【蓝桥日记⑤】2014第五届省赛&#xff08;软件类&#xff09;JavaA组☃答案解析1、猜年龄2、李白打酒3、神奇算式4、写日志5、锦标赛6、六角填数7、绳圈8、兰顿蚂蚁9、斐波那契10、波动…...

Leetcode.1139 最大的以 1 为边界的正方形

题目链接 Leetcode.1139 最大的以 1 为边界的正方形 Rating &#xff1a; 1744 题目描述 给你一个由若干 0 和 1 组成的二维网格 grid&#xff0c;请你找出边界全部由 1 组成的最大 正方形 子网格&#xff0c;并返回该子网格中的元素数量。 如果不存在&#xff0c;则返回 0。…...

Bing+ChatGPT 对传统搜索引擎的降维打击

早些时候申请了新版 Bing 的内测资格&#xff0c;终于收到了通过的邮件。 一天的体验之后&#xff0c;我的感受是&#xff1a;当新版 Bing 具备了 ChatGPT 的聊天能力之后&#xff0c;它的能力不论是对传统搜索引擎&#xff0c;还是 ChatGPT 自身&#xff0c;都将是降维打击。 …...

【JS】数组常用方法总结-功能、参数、返回值

数组常用方法总结-功能、参数、返回值 用简单的js示例 运行在线工具&#xff1a;链接: 菜鸟工具 菜鸟工具示意图&#xff1a; ![在这里插入图片描述](https://img-blog.csdnimg.cn/de8589eb1acf42abb0347d8a3a3bbdfa.png 1.会改变原有数组方法 &#xff08;1&#xff09;pu…...

pytest 单元测试前后置处理

文章目录方法1 setup/teardown方法2 fixture 夹具方法3 conftest.py测试用例执行前后的一些处理动作&#xff0c;也叫夹具。以下介绍使用前后置操作的几种方法。方法1 setup/teardown setup&#xff0c;每个测试用例执行前要进行的处理。 teardown&#xff0c;每个测试用例执行…...

汽车安全硬件扩展 AUTOSAR SHE SecureHardwareExtensions

SHE&#xff08;Secure Hardware Extension&#xff09;在车联网中&#xff0c;被应用在车端ECU中负责安全存储与安全计算。是由HIS&#xff08;由Audi、BMW、Porsche、Volkswagen组成&#xff09;制定的标准&#xff0c;中文意思“安全硬件扩展”&#xff0c;是对任何给定微控…...

2023年美国大学生数学建模C题:预测Wordle结果建模详解+模型代码

目录 前言 一、题目理解 背景 解析 字段含义&#xff1a; 建模要求 二、建模思路 灰色预测&#xff1a; ​编辑 二次指数平滑法&#xff1a; person相关性 只希望各位以后遇到建模比赛可以艾特认识一下我&#xff0c;我可以提供免费的思路和部分源码&#xff0c;以后…...

5、HAL库驱动W25Qxx

一、 SPI通信驱动W25Qxx 1、使用驱动文件快速配置工程代码驱动W25Qxx &#xff08;此驱动文件只适合W25Qxx 16M及以下型号&#xff0c;因为访问地址位数不同&#xff09; 注&#xff1a;本次使用SPI的方式进行访问W25Qxx Flash进行数据读写&#xff0c;关于W25Qxx芯片不会做…...

git rebase 洐合(变基)

洐合 把一个分支整合到另一个分支的办法有两种&#xff1a;merge&#xff08;合并&#xff09; 和 rebase&#xff08;衍合&#xff09; 为什么使用&#xff1f; 使提交记录更简洁 三种情况 第一种&#xff1a; 合并多条commit记录 git rebase -i HEAD~合并数量 HEAD~3&a…...

Kubernetes 1.18学习笔记

文章目录一、Kubernetes 概述和架构1、kubernetes 基本介绍2、Kubernetes 功能3、Kubernetes 架构组件4、Kubernetes 核心概念5、Kubernetes 工作原理二、Kubernetes 集群搭建1、系统环境准备1.1 安装要求1.2 系统初始化2、客户端工具kubeadm搭建2.1 安装步骤2.2 安装组件2.3 集…...

AJAX技术

AJAX技术 浏览器是多进程的&#xff0c;简单的说就是&#xff0c;浏览器每打开一个标签页&#xff0c;就相当于创建了一个独立的浏览器进程。但是js是基于单线程的&#xff0c;而这个线程就是浏览器的js引擎&#xff0c;浏览器无论在什么时候都只且只有一个线程在运行JavaScri…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

JS设计模式(4):观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...