链表学习之反转链表
链表解题技巧
- 额外的数据结构(哈希表);
- 快慢指针;
- 虚拟头节点;
反转链表
分别实现单向链表和双向链表的反转。
要求:长度为N的链表,时间复杂度为O(N),额外空间复杂度为O(1)。
反转单向链表:
方法1(使用栈,时:O(N),空:O(N)):
- 第一次遍历将数据添加至栈中;
- 定义一个空节点,tmp记录,cur指向该节点;
- 栈不为空开始循环出栈:
- cur的next指向的栈顶元素;
- 栈顶元素出栈;
- cur移动到next的位置;
- cur现在在最后一个位置,将其next赋值为nullptr;
- cur指向tmp(空节点)的next位置,并删除tmp;
- 返回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)):
双指针解法:
- 定义两个指针new_head,cur,初始new_head指向head,cur指向head的next;
- cur不为nullptr则开始循环:
- head的next赋值为cur的next;
- cur的next赋值为new_head;
- new_head移动到cur;
- cur移动到head的next;
- 最后返回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;
}
相关文章:
链表学习之反转链表
链表解题技巧 额外的数据结构(哈希表);快慢指针;虚拟头节点; 反转链表 分别实现单向链表和双向链表的反转。 要求:长度为N的链表,时间复杂度为O(N),额外空间复杂度为O(1)。 反转…...
ONNXRUNTUIME实例分割网络说明
ONNXRUNTUIME c使用(分割网络)与相关资料(暂记) initiate a env with an id name(使用id名称启动env) create session (创建会话 ) onnxenv -> sessioninputname [“x”] ,outputname [“t”]inputnodedim [[1,1,192,192…...
几行代码,就写完懒加载啦?
Ⅰ、前言 「懒加载」是网页中非常 常见的;为了减少系统的压力,对于一些电商系统出场频率非常高;那么大家一般用什么方式去实现 「懒加载」 呢 ? ① 通过 scroll 的形式: 通过 滚动「scroll」事件,然后去判…...
PyTorch常用的损失函数(ChatGPT)
L1Loss nn.L1Loss 也称为平均绝对误差(Mean Absolute Error,MAE)。它计算预测值与真实值之间的差异(即误差),然后取绝对值并求和,最后除以样本数量得到平均误差。具体来说,对于一批…...
LeetCode——1237. 找出给定方程的正整数解
一、题目 来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/find-positive-integer-solution-for-a-given-equation/description/ 翻译一下题目 意思是,这是一个二维单调递增的函数,函数一共有 9 …...
系统编程中的进程的概念No.3【进程状态】
引言: 北京时间:2023/2/17/8:17,目前听着超能陆战队主题曲《Immortals》,感觉又要螺旋式升天,并且为我今天上午没课感到happy,所以继我们很久以前的关于进程的博客,今天我们就再来学习一下有关…...
推荐 3 款 Golang 语义化版本库
文章目录1.什么是语义化版本 2.0.02.Golang 语义化版本库比较3.小结参考文献1.什么是语义化版本 2.0.0 语义化版本 2.0.0(Semantic Versioning 2.0.0)是一种用于标识软件版本的约定和规范。它包含三个数字组成的版本号,格式为“MAJOR.MINOR.…...
Windows平台使用gdb连接qemu虚拟机上的系统
先安装MinGW; 除了gcc、g,把gdb也选上;可能选第一个就可以了,不清楚把后面几个也选上; 安装完成看一下gcc, g,gdb,编译工具和调试器都有了; 把bin目录加到环境变量; 看一…...
【博客624】MAC地址表、ARP表、路由表(RIB表)、转发表(FIB表)
MAC地址表、ARP表、路由表(RIB表/FIB表) MAC地址表 MAC地址表是交换机等网络设备记录MAC地址和端口的映射关系,代表了交换机从哪个端口学习到了某个MAC地址,交换机把这个信息记录下来,后续交换机需要转发数据的时候就可以根据报文的目的MAC地…...
【蓝桥日记⑤】2014第五届省赛(软件类)JavaA组❆答案解析
【蓝桥日记⑤】2014第五届省赛(软件类)JavaA组☃答案解析 文章目录【蓝桥日记⑤】2014第五届省赛(软件类)JavaA组☃答案解析1、猜年龄2、李白打酒3、神奇算式4、写日志5、锦标赛6、六角填数7、绳圈8、兰顿蚂蚁9、斐波那契10、波动…...
Leetcode.1139 最大的以 1 为边界的正方形
题目链接 Leetcode.1139 最大的以 1 为边界的正方形 Rating : 1744 题目描述 给你一个由若干 0 和 1 组成的二维网格 grid,请你找出边界全部由 1 组成的最大 正方形 子网格,并返回该子网格中的元素数量。 如果不存在,则返回 0。…...
Bing+ChatGPT 对传统搜索引擎的降维打击
早些时候申请了新版 Bing 的内测资格,终于收到了通过的邮件。 一天的体验之后,我的感受是:当新版 Bing 具备了 ChatGPT 的聊天能力之后,它的能力不论是对传统搜索引擎,还是 ChatGPT 自身,都将是降维打击。 …...
【JS】数组常用方法总结-功能、参数、返回值
数组常用方法总结-功能、参数、返回值 用简单的js示例 运行在线工具:链接: 菜鸟工具 菜鸟工具示意图: pu…...
pytest 单元测试前后置处理
文章目录方法1 setup/teardown方法2 fixture 夹具方法3 conftest.py测试用例执行前后的一些处理动作,也叫夹具。以下介绍使用前后置操作的几种方法。方法1 setup/teardown setup,每个测试用例执行前要进行的处理。 teardown,每个测试用例执行…...
汽车安全硬件扩展 AUTOSAR SHE SecureHardwareExtensions
SHE(Secure Hardware Extension)在车联网中,被应用在车端ECU中负责安全存储与安全计算。是由HIS(由Audi、BMW、Porsche、Volkswagen组成)制定的标准,中文意思“安全硬件扩展”,是对任何给定微控…...
2023年美国大学生数学建模C题:预测Wordle结果建模详解+模型代码
目录 前言 一、题目理解 背景 解析 字段含义: 建模要求 二、建模思路 灰色预测: 编辑 二次指数平滑法: person相关性 只希望各位以后遇到建模比赛可以艾特认识一下我,我可以提供免费的思路和部分源码,以后…...
5、HAL库驱动W25Qxx
一、 SPI通信驱动W25Qxx 1、使用驱动文件快速配置工程代码驱动W25Qxx (此驱动文件只适合W25Qxx 16M及以下型号,因为访问地址位数不同) 注:本次使用SPI的方式进行访问W25Qxx Flash进行数据读写,关于W25Qxx芯片不会做…...
git rebase 洐合(变基)
洐合 把一个分支整合到另一个分支的办法有两种:merge(合并) 和 rebase(衍合) 为什么使用? 使提交记录更简洁 三种情况 第一种: 合并多条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技术 浏览器是多进程的,简单的说就是,浏览器每打开一个标签页,就相当于创建了一个独立的浏览器进程。但是js是基于单线程的,而这个线程就是浏览器的js引擎,浏览器无论在什么时候都只且只有一个线程在运行JavaScri…...
从“密码药丸”看生物识别与人体通信技术的工程伦理边界
1. 项目概述:当身份认证变成一颗“药丸”在消费电子领域,厂商们为了寻求产品差异化,常常会探索一些听起来像是科幻小说的技术路径。大约十年前,一个由DARPA背景的工程师团队提出的概念——“密码药丸”,就曾引发过一场…...
手把手图解:用‘阻挫’和‘复本’理解自旋玻璃、自旋冰与量子自旋液体
手把手图解:用‘阻挫’和‘复本’理解自旋玻璃、自旋冰与量子自旋液体 凝聚态物理中那些看似晦涩的概念,往往只需要一个恰到好处的比喻就能豁然开朗。想象你正在参加一场磁铁小人的派对,它们的箭头方向就像固执的舞伴,既想跟随音乐…...
LaTeX公式转换终极指南:3分钟搞定Word数学公式的免费Chrome扩展
LaTeX公式转换终极指南:3分钟搞定Word数学公式的免费Chrome扩展 【免费下载链接】LaTeX2Word-Equation Copy LaTeX Equations as Word Equations, a Chrome Extension 项目地址: https://gitcode.com/gh_mirrors/la/LaTeX2Word-Equation 还在为学术论文中复杂…...
5分钟完全掌握ncmdump:专业解密网易云NCM格式实现音乐自由
5分钟完全掌握ncmdump:专业解密网易云NCM格式实现音乐自由 【免费下载链接】ncmdump 项目地址: https://gitcode.com/gh_mirrors/ncmd/ncmdump ncmdump是一款专业的网易云音乐NCM格式解密工具,能够将加密的NCM音频文件转换为通用的MP3格式&#…...
微信网页版访问难题如何破解?wechat-need-web浏览器扩展的轻量级替代方案探索
微信网页版访问难题如何破解?wechat-need-web浏览器扩展的轻量级替代方案探索 【免费下载链接】wechat-need-web 让微信网页版可用 / Allow the use of WeChat via webpage access 项目地址: https://gitcode.com/gh_mirrors/we/wechat-need-web 你是否曾在公…...
AI代理如何通过MCP协议实现DeFi自动化操作与安全交互
1. 项目概述:当DeFi遇上AI代理,一场链上金融的自动化革命如果你和我一样,在DeFi(去中心化金融)世界里摸爬滚打了好几年,从早期的流动性挖矿到后来的各种收益聚合器,一个深刻的体会是:…...
Rust微信SDK实战:构建高性能、类型安全的微信机器人
1. 项目概述与核心价值 最近在折腾一些需要与微信生态深度交互的自动化项目,比如自动回复、消息监控、群管理工具等。这类需求在电商客服、社群运营、企业内部流程自动化等场景下非常普遍。传统的做法往往是基于官方提供的HTTP API,自己封装请求、处理复…...
[特殊字符] 论文查重还在花钱?这个AI平台凭什么敢免费?一条给你讲透
各位正在跟论文死磕的朋友们,今天咱们不聊选题,不聊文献,聊一个每个毕业生都绑不开的刚需——查重。 你有没有算过一笔账?本科论文查一次少说三四十,硕士论文动辄上百,有些平台甚至标价两三百。一篇论文改…...
PLINK实战:如何用--het和--hardy参数快速筛查异常样本与SNP位点
PLINK实战:基因组数据质控中的杂合度与哈迪-温伯格平衡分析技巧 拿到测序数据的第一天,实验室新来的博士生盯着满屏的PLINK报表面露难色——那些F值、P值究竟在说什么?为什么隔壁组的文章用0.2过滤杂合度,而合作方坚持要用0.1&…...
长期使用Taotoken的Token Plan套餐在项目成本控制上的实际感受
🚀 告别海外账号与网络限制!稳定直连全球优质大模型,限时半价接入中。 👉 点击领取海量免费额度 长期使用Taotoken的Token Plan套餐在项目成本控制上的实际感受 1. 项目背景与成本挑战 在持续数月的项目开发与迭代过程中&#x…...
