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

剑指 Offer Day2——链表(简单)

目录

  • 剑指 Offer 06. 从尾到头打印链表
  • 剑指 Offer 24. 反转链表
  • 剑指 Offer 35. 复杂链表的复制

剑指 Offer 06. 从尾到头打印链表

原题链接:06. 从尾到头打印链表

最容易想到的思路就是先从头到尾打印下来,然后 reverse 一下,但这里我们使用递归。

class Solution {
public:vector<int> reversePrint(ListNode *head) {if (head == nullptr) return {};auto res = reversePrint(head->next);res.push_back(head->val);return res;}
};

递归的缺点是元素一多容易爆栈,我们还可以利用栈的特性来完成这道题。

剑指 Offer 24. 反转链表

原题链接:24. 反转链表

递归解法(清晰易懂):

class Solution {
public:ListNode *reverseList(ListNode *head) {if (!head || !head->next) return head;auto newHead = reverseList(head->next);head->next->next = head;head->next = nullptr;return newHead;}
};

当链表长度为 000111 时,无需反转。

考虑链表 1→2→3→4→∅1\to2\to3\to4\to\varnothing1234,当调用 reverseList(1->next) 后,链表变成 1→2←3←41\to2\leftarrow3\leftarrow41234,此时需要让 222 指向 111,即 2->next = 1,相当于 1->next->next = 1,之后还需要让 111 指向 ∅\varnothing,即 1->next = nullptr

迭代解法:

class Solution {
public:ListNode *reverseList(ListNode *head) {ListNode *pre = nullptr;ListNode *cur = head;while (cur) {ListNode *tmp = cur->next;cur->next = pre;pre = cur;cur = tmp;}return pre;}
};

设置两个指针,每次让后一个节点指向前一个节点,然后两个指针同时右移一位。

剑指 Offer 35. 复杂链表的复制

原题链接:35. 复杂链表的复制

我们先来看一下普通链表是如何复制的。

class Node {
public:int val;Node *next;Node() : val(0), next(nullptr) {}Node(int _val) : val(_val), next(nullptr) {}Node(int _val, Node *_next) : val(_val), next(_next) {}
};class Solution {
public:Node *copyList(Node *head) {Node *cur = head;Node *dummy = new Node(-1), *pre = dummy;while (cur) {Node *newNode = new Node(cur->val);pre->next = newNode;cur = cur->next, pre = pre->next;  // cur在原链表上移动,pre在新链表上移动}return dummy->next;}
};

因为普通链表只有一个 next 指针且指向下一个节点,所以我们可以用迭代的方法复制一个普通链表(当然也可以递归)。但是复杂链表还有一个 random 指针指向随机一个节点,所以迭代方法失效。

我们可以通过哈希表来建立原链表和新链表之间的对应关系,具体来说,map[原链表中的某个节点] = 新链表中相应的节点,这样就可以随机访问新链表中的节点了。

class Solution {
public:Node *copyRandomList(Node *head) {if (!head) return head;unordered_map<Node *, Node *> map;Node *cur = head;while (cur) {map[cur] = new Node(cur->val);cur = cur->next;}cur = head;while (cur) {map[cur]->next = map[cur->next];map[cur]->random = map[cur->random];cur = cur->next;}return map[head];}
};

相关文章:

剑指 Offer Day2——链表(简单)

目录剑指 Offer 06. 从尾到头打印链表剑指 Offer 24. 反转链表剑指 Offer 35. 复杂链表的复制剑指 Offer 06. 从尾到头打印链表 原题链接&#xff1a;06. 从尾到头打印链表 最容易想到的思路就是先从头到尾打印下来&#xff0c;然后 reverse 一下&#xff0c;但这里我们使用递归…...

Final Cut Pro 10.6.5

软件介绍Final Cut Pro 10.6.5 已通过小编安装运行测试 100%可以使用。Final Cut Pro 10.6.5 破解版启用了全新的矩形图标&#xff0c;与最新的macOS Ventura设计风格统一&#xff0c;支持最新的macOS 13 文图拉系统&#xff0c;支持Apple M1/M2芯片。经过完整而彻底的重新设计…...

Modelsim仿真操作指导

目录 一、前言 二、仿真分类 三、RTL级仿真 3.1创建库 3.2 仿真配置设置 3.3 运行仿真 四、常见问题 4.1 运行仿真时报错“cant read "Startup(-L)": no such element in array” 4.2 运行仿真时无任何报错&#xff0c;但object窗口为空&#xff0c;可正常运…...

你知道这20个数组方法是怎么实现的吗?

前言你们一定对JavaScript中的数组很熟悉&#xff0c;我们每天都会用到它的各种方法&#xff0c;比如push、pop、forEach、map……等等。但是仅仅使用它就足够了吗&#xff1f;如此出色&#xff0c;您一定不想停在这里。我想和你一起挑战实现20数组方法的功能。1、forEachforEa…...

《系统架构设计》-01-架构和架构师概述

文章目录1. 架构的基本定义1.1 架构组成理论1.1.1 系统元素1&#xff09;概念2&#xff09;静态结构和动态结构1.1.2 基本系统属性1.1.3 设计和发展原则1.2 架构的决策理论1.2.1 统一软件过程&#xff08;Rational Unified Process&#xff0c;统一软件过程&#xff09;1.2.2 决…...

第七届蓝桥杯省赛——5分小组

题目&#xff1a;9名运动员参加比赛&#xff0c;需要分3组进行预赛。有哪些分组的方案呢&#xff1f;我们标记运动员为 A,B,C,... I下面的程序列出了所有的分组方法。该程序的正常输出为&#xff1a;ABC DEF GHIABC DEG FHIABC DEH FGIABC DEI FGHABC DFG EHIABC DFH EGIABC DF…...

中国专科医院行业市场规模及未来发展趋势

中国专科医院行业市场规模及未来发展趋势中国专科医院行业在过去几年中取得了跨越式发展&#xff0c;市场规模不断扩大&#xff0c;未来的发展前景也远比过去更加乐观。根据市场调研在线网发布的2023-2029年中国专科医院行业运营现状及发展前景预测报告分析,截至2018年&#xf…...

【刷题笔记】--两数之和Ⅳ,从二叉树中找出两数之和

法一&#xff1a;深度搜索中序遍历双指针 思路&#xff1a;通过中序遍历二叉树得到一个递增的数列&#xff0c;再在这个递增的二叉树中找到这两数。 主要学到双指针这个方法。 对于一般数列&#xff0c;我们要找到两数满足其之和等于目标数&#xff0c;我们一般会进行暴力&a…...

浏览器渲染原理JavaScript V8引擎

浏览器渲染原理 前言 在我们面试过程中&#xff0c;面试官经常会问到这么一个问题&#xff0c;那就是从在浏览器地址栏中输入URL到页面显示&#xff0c;浏览器到底发生了什么&#xff1f; 浏览器内有哪些进程&#xff0c;这些进程都有些什么作用&#xff1b;浏览器地址输入U…...

在TheSandbox 的「BOYS PLANET」元宇宙中与你的男孩们见面吧!

世界各的男孩们成为 K-Pop 男团的旅程。 Mnet 的全球项目 BOYS PLANET 终于在 2 月 2 日首次亮相&#xff01; The Sandbox 与 CJ ENM 合作&#xff0c;于 2 月 6 日晚上 10 点开始举办两个基于 BOYS PLANET 生存节目的虚拟体验&#xff1a;BOYS PLANET&#xff1a;BOYS LAND 和…...

数据结构与算法:java对象的比较

1.基本类型的比较 在Java中&#xff0c;基本类型的对象可以直接比较大小。 public class TestCompare {public static void main(String[] args) {int a 10;int b 20;System.out.println(a > b);System.out.println(a < b);System.out.println(a b);char c1 A;char…...

python(16)--类

一、类的基本操作1.定义一个类格式&#xff1a;class Classname( )&#xff1a;内容&#x1f48e;鄙人目前还是一名学生&#xff0c;最熟悉的也就是学校了&#xff0c;所以就以学校为例子来建立一个类吧class School():headline"帝国理工大学"def schoolmotto(self):…...

CNI 网络流量分析(七)Calico 介绍与原理(二)

文章目录CNI 网络流量分析&#xff08;七&#xff09;Calico 介绍与原理&#xff08;二&#xff09;CNIIPAM指定 IP指定非 IPAM IPCNI 网络流量分析&#xff08;七&#xff09;Calico 介绍与原理&#xff08;二&#xff09; CNI 支持多种 datapath&#xff0c;默认是 linuxDa…...

API安全的最大威胁:三体攻击

最近《三体》火的一塌糊涂,动画片、电视剧和书都受到了大家的喜爱。在API安全上,最近也发现了三体攻击。 当然了,肯定是不来自于三体人的攻击,这里的三体攻击指的是(trinity,也称三位一体攻击),是一个新的攻击手法。具体的情况老李也找到了相关的介绍,下面就分享给大…...

分布式事务解决方案——TCC

TCC是Try、Confirm、Cancel三个词语的缩写&#xff0c;TCC要求每个分支事务实现三个操作&#xff1a;预处理Try、确认Confirm、撤销Cancel。1、Try 阶段是做业务检查(一致性)及资源预留(隔离)&#xff0c;此阶段仅是一个初步操作&#xff0c;它和后续的Confirm一起才能真正构成…...

ITSS认证分为几个级别,哪个级别最高

​一、什么是ITSS ITSS( 信息技术服务标准&#xff0c;简称ITSS)是国内第一套成体系和综合配套的信息技术服务标准库&#xff0c;全面规范了IT服务产品及其组成要素&#xff0c;用于指导实施标准化和可信赖的IT服务。 ITSS是在工业和信息化部、国家标准化管理委员会的联合指导下…...

ZigBee案例笔记 - USART

文章目录1.串行通信接口简述2.串行通信接口寄存器U0CSR (0x86) -USART 0 控制和状态U0UCR (0xC4)–USART 0 UART 控制U0GCR (0xC5)–USART 0 通用控制U0BUF (0xC1) – USART 0 接收/传送数据缓存U0BAUD (0xC2) – USART 0 波特率控制3.设置串行通信接口比特率控制寄存器4.外设I…...

java | 基于Redis的分布式锁实现①

前言 首先&#xff0c;为了确保分布式锁可用&#xff0c;我们至少要确保锁的实现同时满足以下四个条件&#xff1a; 互斥性。在任意时刻&#xff0c;只有一个客户端能持有锁。不会发生死锁。即使有一个客户端在持有锁的期间崩溃而没有主动解锁&#xff0c;也能保证后续其他客户…...

十六、基于FPGA的CRC校验设计实现

1&#xff0c;CRC校验循环冗余校验&#xff08;Cyclic Redundancy Check&#xff0c; CRC&#xff09;是一种根据网络数据包或计算机文件等数据产生简短固定位数校验码的一种信道编码技术&#xff0c;主要用来检测或校验数据传输或者保存后可能出现的错误。它是利用除法及余数的…...

2022爱分析 · DataOps厂商全景报告 | 爱分析报告

报告编委 李喆 爱分析合伙人&首席分析师 廖耘加 爱分析分析师 目录 1. 研究范围定义 2. 市场洞察 3. 厂商全景地图 4. 市场分析与厂商评估 5. 入选厂商列表 1. 研究范围定义 研究范围 在后疫情时代&#xff0c;以数据分析为代表的数据消费场景日益丰富&…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

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

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

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...