【数据结构】两两交换链表 复制带随机指针的链表

问题描述1

给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

求解

使用一个栈S来存储相邻两个节点即可
在这里插入图片描述

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* swapPairs(ListNode* head) {stack<ListNode*> s;if(head==nullptr || head->next == nullptr){return head;}ListNode * p = new ListNode();ListNode * cur = head;head = p;while(cur!=nullptr && cur->next !=nullptr){s.push(cur);s.push(cur->next);cur = cur->next->next;p->next = s.top();s.pop();p = p->next;p->next = s.top();s.pop();p = p->next;}if(cur==nullptr){p->next = nullptr;}else if(cur->next == nullptr){p->next = cur;}return head->next;}
};

问题描述2

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:

val:一个表示 Node.val 的整数。
random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

求解

使用哈希表。
利用哈希表的查询特点,考虑构建 原链表节点 和 新链表对应节点 的键值对映射关系,再遍历构建新链表各节点的 next 和 random 引用指向即可。

/*
// Definition for a Node.
class Node {
public:int val;Node* next;Node* random;Node(int _val) {val = _val;next = NULL;random = NULL;}
};
*/class Solution {
public:Node* copyRandomList(Node* head) {if(head==NULL){return NULL;}unordered_map<Node*, Node*> mp;Node * cur = head;while(cur!=NULL){mp[cur] = new Node(cur->val);cur = cur->next;}cur =  head;while(cur !=NULL){mp[cur]->next = mp[cur->next];mp[cur]->random = mp[cur->random];cur = cur->next;}return mp[head];}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/305665.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

5G-A有何能耐?5G-A三载波聚合技术介绍

2024年被称作5G-A元年。5G-A作为5G下一阶段的演进技术&#xff0c;到底有何能耐呢&#xff1f; 三载波聚合&#xff08;3CC&#xff09;被认为是首个大规模商用的5G-A技术&#xff0c;将带来手机网速的大幅提升。 █ 什么是3CC 3CC&#xff0c;全称叫3 Component Carriers…

Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单视频处理实战案例 之九 简单视频卡通画效果

Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单视频处理实战案例 之九 简单视频卡通画效果 目录 Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单视频处理实战案例 之九 简单视频卡通画效果 一、简单介绍 二、简单视频卡通画效果实现原理 三、简单视频卡通画效果…

spring.rabbitmq.listener.simple.default-requeue-rejected = false 和放入死信队列的区别

目录 一、场景 二、使用 spring.rabbitmq.listener.simple.default-requeue-rejected false 2.1 特点 三、 放入死信队列 四、两种区别 一、场景 当我们使用RabbitMq的时候&#xff0c;我们如果业务中有异常&#xff0c;很有可能造成死循环&#xff0c;因为 在RabbitMQ和…

【随笔】Git 高级篇 -- 纠缠不清的分支 rebase | cherry-pick(二十四)

&#x1f48c; 所属专栏&#xff1a;【Git】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &#x1f496; 欢迎大…

2024考研调剂须知

----------------------------------------------------------------------------------------------------- 考研复试科研背景提升班 教你快速深入了解掌握考研复试面试中的常见问题以及注意事项&#xff0c;系统的教你如何在短期内快速提升自己的专业知识水平和编程以及英语…

Python+Django+Html网页版人脸识别考勤打卡系统

程序示例精选 PythonDjangoHtml人脸识别考勤打卡系统 如需安装运行环境或远程调试&#xff0c;见文章底部个人QQ名片&#xff0c;由专业技术人员远程协助&#xff01; 前言 这篇博客针对《PythonDjangoHtml网页版人脸识别考勤打卡系统》编写代码&#xff0c;代码整洁&#xf…

单链表总结提升

这篇博客讲解数据结构中的单链表&#xff0c;包括单链表的基础知识和我对链表实现的总结理解&#xff0c;希望可以帮助到正在学习的小伙伴&#xff0c;也希望得到小伙伴们的关注和支持哦~ 目录 1.单链表的概念 1.2顺序表和链表的对比 顺序表&#xff1a; 链表&#xff1a;…

Sketch3D:用于草图到3D生成的样式一致性指南

Sketch3D: Style-Consistent Guidance for Sketch-to-3D Generation Sketch3D&#xff1a;用于草图到3D生成的样式一致性指南 Wangguandong Zheng 重试 错误原因 Southeast UniversityChina 重试 错误原因 wgdzhengseu.edu.cnHaifeng Xia 重试 错误原因 Southeast Universit…

C语言读取 .ico 文件并显示数据

原来是想做光标编辑器&#xff0c;自己把绘图板的内容导出为光标格式 鼠标指针文件格式解析——Windows&#xff08;一&#xff09; (qq.com) 代码来源自 Icons | Microsoft Learn 鄙人又补充些变量可以运行微软的代码 简单代码如下 #include <stdio.h> #include &l…

软考高级架构师:数据库模式概念和例题

一、AI 讲解 数据库模式分为三个层次&#xff1a;外模式、概念模式和内模式。这三个层次分别对应不同的抽象级别&#xff0c;帮助数据库管理员和用户以不同的视角理解数据库结构。 外模式&#xff08;用户级&#xff09;&#xff1a;是数据库用户的视图。每个用户可以通过外模…

最新Android Studio导入aar包的方法

以前的方式&#xff0c;目前看网上也大多数都是这种方式&#xff0c;导致我本地加的时候一直有问题 但是这样都无法sync以及编译通过&#xff0c;因为方式已经变了 1&#xff1a;将aar文件复制到MyApplication\app\libs下 2&#xff1a;在MyApplication\app\build.gradle下添加…

LeetCode-Java:6.Z字形变换

文章目录 题目解① 找规律 题目 将一个给定字符串 s 根据给定的行数 numRows &#xff0c;以从上往下、从左到右进行 Z 字形排列。 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时&#xff0c;排列如下&#xff1a; P A H N A P L S I I G Y I R之后&a…

独家原创 | Matlab实现INFO-BiTCN-BiGRU-Attention多输入单输出回归预测

独家原创 | Matlab实现INFO-BiTCN-BiGRU-Attention多输入单输出回归预测 目录 独家原创 | Matlab实现INFO-BiTCN-BiGRU-Attention多输入单输出回归预测效果一览基本介绍程序设计参考资料 效果一览 基本介绍 1.Matlab实现INFO-BiTCN-BiGRU-Attention向量加权算法优化双向时间卷积…

【无人机/平衡车/机器人】详解STM32+MPU6050姿态解算—卡尔曼滤波+四元数法+互补滤波——附3个算法源码

效果&#xff1a; MPU6050姿态解算-卡尔曼滤波四元数互补滤波 目录 基础知识详解 欧拉角 加速度计(Accelerometer)与姿态测量 陀螺仪(Gyroscope)与姿态测量 姿态解算算法1-互补滤波 姿态解算算法2-四元数法 姿态解算算法3-卡尔曼滤波 组成 1.预测状态方程 2. 预测协方…

10:00面试,10:08就出来了,问的问题有点变态。。。

从小厂出来&#xff0c;没想到在另一家公司又寄了。 到这家公司开始上班&#xff0c;加班是每天必不可少的&#xff0c;看在钱给的比较多的份上&#xff0c;就不太计较了。没想到8月一纸通知&#xff0c;所有人不准加班&#xff0c;加班费不仅没有了&#xff0c;薪资还要降40%…

浅谈网络安全威胁与防御策略

企业网络安全威胁概述 外部威胁&#xff1a;来自网络安全威胁&#xff0c;比如DDOS攻击&#xff0c;病毒&#xff0c;sql注入&#xff0c;木马&#xff0c;蠕虫&#xff0c;等网络入侵&#xff0c;网络扫描&#xff0c;垃圾邮件&#xff0c;钓鱼邮件&#xff0c;针对web的攻击…

计算机网络——NAT技术

目录 前言 前篇 引言 SNAT&#xff08;Source Network Address Translation&#xff09;源网络地址转换 SNAT流程 确定性标记 DNAT&#xff08;Destination Network Address Translation&#xff0c;目标网络地址转换&#xff09; NAT技术重要性 前言 本博客是博主用于…

科技论文和会议录制高质量Presentation Video视频方法

一、背景 机器人领域&#xff0c;许多高质量的期刊和会议&#xff08;如IEEE旗下的TRO&#xff0c;RAL&#xff0c;IROS&#xff0c;ICRA等&#xff09;在你的论文收录后&#xff0c;需要上传一个Presentation Video材料&#xff0c;且对设备兼容性和视频质量有较高要求&#…

Vue3基础语法

在这个章节中&#xff0c;简单的看下Vue3的基础语法&#xff0c;有了这些基础后&#xff0c;对写vue3单页也就没有什么问题了。 模板语法 在写html时&#xff0c;我们希望在某个节点绑定一个动态值时&#xff0c;是使用dom操作执行的&#xff0c;如下&#xff1a; <!DOCT…

Linux:动态库加载、编址

目录 一、库的概念 二、动静态库的加载 2.1绝对编址与相对编址 2.1一般程序的加载 三、动态库的加载 一、库的概念 库默认就是一个磁盘级文件&#xff0c;所以在执行代码时&#xff0c;库和可执行程序都会被加载到内存中&#xff0c;从原理上&#xff0c;库函数的调用依旧…