当前位置: 首页 > 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;以数据分析为代表的数据消费场景日益丰富&…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用

在工业制造领域&#xff0c;无损检测&#xff08;NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统&#xff0c;以非接触式光学麦克风技术为核心&#xff0c;打破传统检测瓶颈&#xff0c;为半导体、航空航天、汽车制造等行业提供了高灵敏…...

AI语音助手的Python实现

引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...

springboot 日志类切面,接口成功记录日志,失败不记录

springboot 日志类切面&#xff0c;接口成功记录日志&#xff0c;失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...