当前位置: 首页 > 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…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...