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

剑指 Offer(第2版)面试题 35:复杂链表的复制

剑指 Offer(第2版)面试题 35:复杂链表的复制

  • 剑指 Offer(第2版)面试题 35:复杂链表的复制
    • 解法1:模拟

剑指 Offer(第2版)面试题 35:复杂链表的复制

题目来源:48. 复杂链表的复刻

解法1:模拟

算法:

  1. 复制原始链表的节点 N 并创建新节点 N’,把 N’ 链接到 N 的后面。
  2. 设置复制节点的 random 指针。
  3. 拆分链表:把奇数位置的节点链接起来就是原始链表,把偶数位置的节点链接起来就是复制链表,最后返回复制链表的头节点。

PS:少有的书上代码比其他解法要好的,推荐书上解法,拆分成三步走,清晰明了。

代码:

/*** Definition for singly-linked list with a random pointer.* struct ListNode {*     int val;*     ListNode *next, *random;*     ListNode(int x) : val(x), next(NULL), random(NULL) {}* };*/
class Solution
{
public:ListNode *copyRandomList(ListNode *head){CloneListNodes(head);SetRandomPointer(head);return SplitList(head);}// 第一步:复制原始链表的节点 N 并创建新节点 N',把 N' 链接到 N 的后面void CloneListNodes(ListNode *head){ListNode *p = head;while (p){// 复制节点ListNode *clone = new ListNode(0);clone->val = p->val;clone->next = p->next;clone->random = nullptr;p->next = clone;p = clone->next;}}// 第二步:设置复制节点的 random 指针void SetRandomPointer(ListNode *head){// 如果原始链表上的节点 N 的 random 指针指向 S,// 则它的复制节点 N' 的 random 指针指向 S'ListNode *p = head;while (p){ListNode *clone = p->next;if (p->random)clone->random = p->random->next;p = clone->next;}}// 第三步:拆分链表ListNode *SplitList(ListNode *head){ListNode *p = head;ListNode *cloneListHead = nullptr;ListNode *clone = nullptr;if (p){cloneListHead = p->next;clone = p->next;p->next = clone->next;p = p->next;}while (p){clone->next = p->next;clone = clone->next;p->next = clone->next;p = p->next;}return cloneListHead;}
};

复杂度分析:

时间复杂度:O(n),其中 n 是原始链表的节点个数。算法遍历了每个节点。

空间复杂度:O(n),其中 n 是原始链表的节点个数。算法创建了每个节点的副本。

相关文章:

剑指 Offer(第2版)面试题 35:复杂链表的复制

剑指 Offer(第2版)面试题 35:复杂链表的复制 剑指 Offer(第2版)面试题 35:复杂链表的复制解法1:模拟 剑指 Offer(第2版)面试题 35:复杂链表的复制 题目来源&…...

自定义指令Custom Directives

<script setup langts> import { ref } from "vue"const state ref(false)/*** Implement the custom directive* Make sure the input element focuses/blurs when the state is toggled* */ // 以v开头的驼峰式命名的变量都可以作为一个自定义指令 const VF…...

预测性维护对制造企业设备管理的作用

制造企业设备管理和维护对于生产效率和成本控制至关重要。然而&#xff0c;传统的维护方法往往无法准确预测设备故障&#xff0c;导致生产中断和高额维修费用。为了应对这一挑战&#xff0c;越来越多的制造企业开始采用预测性维护技术。 预测性维护是通过传感器数据、机器学习和…...

华为、新华三、锐捷常用命令总结

华为、新华三、锐捷常用命令总结 一、华为交换机基础配置命令二、H3C交换机的基本配置三、锐捷交换机基础命令配置 一、华为交换机基础配置命令 1、创建vlan&#xff1a; <Quidway> //用户视图&#xff0c;也就是在Quidway模式下运行命令。 <Quidway>system-view…...

链路追踪详解(四):分布式链路追踪的事实标准 OpenTelemetry 概述

目录 OpenTelemetry 是什么&#xff1f; OpenTelemetry 的起源和目标 OpenTelemetry 主要特点和功能 OpenTelemetry 的核心组件 OpenTelemetry 的工作原理 OpenTelemetry 的特点 OpenTelemetry 的应用场景 小结 OpenTelemetry 是什么&#xff1f; OpenTelemetry 是一个…...

Node.js 工作线程与子进程:应该使用哪一个

Node.js 工作线程与子进程&#xff1a;应该使用哪一个 并行处理在计算密集型应用程序中起着至关重要的作用。例如&#xff0c;考虑一个确定给定数字是否为素数的应用程序。如果我们熟悉素数&#xff0c;我们就会知道必须从 1 遍历到该数的平方根才能确定它是否是素数&#xff…...

python matplotlib 三维图形添加文字且不随图形变动而变动

要在三维图形中添加文字并使其不随图形变动而变动&#xff0c;可以使用 annotate() 方法。这个方法可以在三维图形中添加文字&#xff0c;并且可以指定文字的位置、对齐方式和字体大小等属性。 下面是一个示例代码&#xff0c;演示如何在三维图形中添加文字&#xff1a; impo…...

Ubuntu设置kubelet启动脚本关闭swap分区

查看swap分区 swapon -s打开swap分区 swapon -a查看/etc/fstab下所有固化的swap分区&#xff0c;注释 vi /etc/fstab修改kubelet.conf文件 vi /etc/systemd/system/kubelet.service.d/10-kubeadm.conf添加 ExecStartPre/sbin/swapoff -a生效 systemctl daemon-reload sys…...

MySQL数据库存储

MySQL数据库存储 MySQL数据库简介MySQL开发环境MySQL安装图形化界面工具Navicat使用 表的操作表的概念3.2 创建表3.3 修改表 数据的操作-增删改查4.1 增加数据4.2 删除数据4.3 修改数据4.4 查询数据4.4.1 基础查询4.4.2 分组查询和聚合函数4.4.4 having语句4.4.5 排序4.5 多表联…...

verilog语法进阶,时钟原语

概述&#xff1a; 内容 1. 时钟缓冲 2. 输入时钟缓冲 3. ODDR2作为输出时钟缓冲 1. 输入时钟缓冲 BUFGP verilog c代码&#xff0c;clk作为触发器的边沿触发&#xff0c;会自动将clk综合成时钟信号。 module primitive1(input clk,input a,output reg y); always (posed…...

案例069:基于微信小程序的计算机实验室排课与查询系统

文末获取源码 开发语言&#xff1a;Java 框架&#xff1a;SSM JDK版本&#xff1a;JDK1.8 数据库&#xff1a;mysql 5.7 开发软件&#xff1a;eclipse/myeclipse/idea Maven包&#xff1a;Maven3.5.4 小程序框架&#xff1a;uniapp 小程序开发软件&#xff1a;HBuilder X 小程序…...

C语言:将三个数从大到小输出

#include<stdio.h> int main() {int a 0;int b 0;int c 0;printf("请输入abc的值&#xff1a;");scanf_s("%d%d%d", &a, &b, &c);if (b > a){int tmp a;a b;b tmp;}if (c > a){int tmp a;a c;c tmp;}if (b < c){int t…...

基于Hadoop的铁路货运大数据平台设计与应用

完整下载&#xff1a;基于Hadoop的铁路货运大数据平台设计与应用 基于Hadoop的铁路货运大数据平台设计与应用 Design and Application of Railway Freight Big Data Platform based on Hadoop 目录 目录 2 摘要 3 关键词 4 第一章 绪论 4 1.1 研究背景 4 1.2 研究目的与意义 5 …...

Java基础题2:类和对象

1.下面代码的运行结果是&#xff08;&#xff09; public static void main(String[] args){String s;System.out.println("s"s);}A.代码编程成功&#xff0c;并输出”s” B.代码编译成功&#xff0c;并输出”snull” C.由于String s没有初始化&#xff0c;代码不能…...

冒泡排序学习

冒泡排序&#xff08;Bubble Sort&#xff09;是一种简单的排序算法&#xff0c;它通过重复地交换相邻的元素来排序。具体实现如下&#xff1a; 1. 从待排序的数组中的第一个元素开始&#xff0c;依次比较相邻的两个元素。 2. 如果前一个元素大于后一个元素&#xff0c;则交换…...

LeetCode(65)LRU 缓存【链表】【中等】

目录 1.题目2.答案3.提交结果截图 链接&#xff1a; LRU 缓存 1.题目 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类&#xff1a; LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 k…...

网站提示“不安全”

当你在浏览网站时&#xff0c;有时可能会遇到浏览器提示网站不安全的情况。这通常是由于网站缺乏SSL证书所致。那么&#xff0c;从SSL证书的角度出发&#xff0c;我们应该如何解决这个问题呢&#xff1f; 首先&#xff0c;让我们简单了解一下SSL证书。SSL证书是一种用于保护网站…...

【Linux】驱动

驱动 驱动程序过程 系统调用 用户空间 内核空间 添加驱动和调用驱动 驱动程序是如何调用设备硬件 驱动 在计算机领域&#xff0c;驱动&#xff08;Driver&#xff09;是一种软件&#xff0c;它充当硬件设备与操作系统之间的桥梁&#xff0c;允许它们进行通信和协同工作。驱动程…...

Java研学-HTML

HTML 1 介绍 HTML(Hypertext Markup Language) 超文本标记语言。静态网页&#xff0c;用于在浏览器上显示数据 超文本: 指页面内可以包含图片、链接&#xff0c;甚至音乐、程序等非文字元素。 标记语言: 使用 < > 括起来的语言 超文本标记语言的结构, 包括“头”部分&am…...

SpringBoot之响应的详细解析

2. 响应 前面我们学习过HTTL协议的交互方式&#xff1a;请求响应模式&#xff08;有请求就有响应&#xff09; 那么Controller程序呢&#xff0c;除了接收请求外&#xff0c;还可以进行响应。 2.1 ResponseBody 在我们前面所编写的controller方法中&#xff0c;都已经设置了…...

2026年南京本地实测整理,值得入手的高性价比全屋定制品牌推荐

讲真&#xff0c;南京准备装房子、换柜子的姊妹们、老少爷们&#xff0c;谁没为全屋定制头大过&#xff1f;刚收了江北核心区的新房&#xff0c;还是鼓楼老破小准备翻新&#xff0c;跑了三五家门店就会发现&#xff1a;水太深了&#xff01;低价套餐勾你进去&#xff0c;签约后…...

在 CentOS 7/8 上部署 NVIDIA Container Toolkit:打通 AI 容器化开发环境

1. 为什么需要NVIDIA Container Toolkit&#xff1f; 如果你正在CentOS服务器上折腾AI开发&#xff0c;肯定遇到过这样的场景&#xff1a;好不容易配好了Docker环境&#xff0c;却发现容器里的TensorFlow死活识别不到GPU。这时候就需要NVIDIA Container Toolkit来打通任督二脉…...

IEA-15-240-RWT:15MW海上风机开源模型的完整入门指南

IEA-15-240-RWT&#xff1a;15MW海上风机开源模型的完整入门指南 【免费下载链接】IEA-15-240-RWT 15MW reference wind turbine repository developed in conjunction with IEA Wind 项目地址: https://gitcode.com/gh_mirrors/ie/IEA-15-240-RWT 你是否曾经想要研究海…...

弹球打砖块

<!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0, user-scalableno"><title>弹球打砖块</title><…...

别再手动数脉冲了!用STM32定时器编码器模式搞定增量编码器(附CubeMX配置)

STM32硬件编码器模式实战&#xff1a;精准捕获增量编码器信号的工程指南 在电机控制、机器人关节定位和精密测量系统中&#xff0c;增量式编码器作为核心反馈元件&#xff0c;其信号处理质量直接影响整个系统的控制精度。传统的中断计数方式在高速脉冲场景下往往捉襟见肘&#…...

WinHex不只是编辑器:手把手教你用它做磁盘镜像与克隆(避坑指南)

WinHex专业磁盘镜像与克隆实战指南&#xff1a;从取证备份到避坑技巧 1. 为什么WinHex是磁盘操作的首选利器 在数据恢复和取证领域&#xff0c;专业工具的选择往往决定了工作的成败。WinHex作为一款久经考验的十六进制编辑器&#xff0c;其功能远超出普通用户的想象。不同于常规…...

深度解析网易游戏NPK文件解包:从二进制迷宫到资源提取的完整实战指南

深度解析网易游戏NPK文件解包&#xff1a;从二进制迷宫到资源提取的完整实战指南 【免费下载链接】unnpk 解包网易游戏NeoX引擎NPK文件&#xff0c;如阴阳师、魔法禁书目录。 项目地址: https://gitcode.com/gh_mirrors/un/unnpk 你是否曾经好奇网易热门游戏如《阴阳师》…...

2026年企业制品管理平台选型推荐:Gitee Repo 如何构建安全高效协作基石

在软件研发的关键环节中&#xff0c;制品管理正经历着从基础存储工具向安全可信协作中枢的深刻演进。面对开源风险、跨团队协作效率与版本追溯等多重挑战&#xff0c;企业对于一套能够深度守护制品安全并支撑高效协同的解决方案需求迫切。Gitee Repo 制品管理平台凭借其全面的能…...

可视化大屏怎么做?可视化大屏工具你会用吗?

可视化大屏早已不只是技术人员的专属&#xff0c;越来越多的运营、产品和市场人也开始尝试&#xff0c;但是常常陷入各种问题&#xff1a;比如硬件效果一般、数据堆积没重点、动效杂乱干扰信息传达……其实归根结底&#xff0c;这些问题都指向一个核心&#xff1a;缺少一个专业…...

AppleRa1n终极指南:3步免费绕过iOS 15-16激活锁限制

AppleRa1n终极指南&#xff1a;3步免费绕过iOS 15-16激活锁限制 【免费下载链接】applera1n icloud bypass for ios 15-16 项目地址: https://gitcode.com/gh_mirrors/ap/applera1n 你是否正为忘记Apple ID密码而无法使用自己的iPhone而烦恼&#xff1f;或者购买的二手苹…...