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

链表OJ(一)

目录

从尾到头打印链表_牛客题霸_牛客网

160. 相交链表

 141. 环形链表

 142. 环形链表 II

138. 复制带随机指针的链表



从尾到头打印链表_牛客题霸_牛客网

输入一个链表的头节点,按链表从尾到头的顺序返回每个节点的值(用数组返回)。

如输入{1,2,3}的链表如下图:

返回一个数组为[3,2,1]

0 <= 链表长度 <= 10000

 【解法一】没学过c++时  反转计数+创建数组

* struct ListNode {*	int val;*	struct ListNode *next;* };*/int* printListFromTailToHead(struct ListNode* listNode, int* returnSize ) {// write code here// 反转链表if(NULL == listNode)return NULL;struct ListNode* cur = listNode;struct ListNode* next = listNode;struct ListNode* prev = NULL;int count = 0;while(cur){count++;next = cur->next;cur->next = prev;prev = cur;cur = next;}// 计数存入数组int *temp = (int *)malloc(sizeof(int)*count);for(int i = 0; i < count; i++){temp[i] = prev->val;prev = prev->next;}*returnSize = count;return temp;
}

【解法二】 遍历一遍 放入vector进行反转

class Solution {
public:vector<int> printListFromTailToHead(ListNode* head) {vector<int> res;if(head==nullptr)return res;ListNode* cur = head;while(cur){res.push_back(cur->val);cur = cur->next;}reverse(res.begin(), res.end());return res;}
};

【解法三】DFS

class Solution {
public:vector<int> res;void DFS(ListNode* cur){if(cur){DFS(cur->next);res.push_back(cur->val);}}vector<int> printListFromTailToHead(ListNode* head) {DFS(head);return res;}
};

【解法四】一次遍历入栈,之后把元素出栈入数组

class Solution {
public:vector<int> printListFromTailToHead(ListNode* head) {vector<int> res;stack<int> s;while(head){s.push(head->val);head=head->next;}while(!s.empty()){res.push_back(s.top());s.pop();}return res;}
};

160. 相交链表

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。

图示两个链表在节点 c1 开始相交:

题目数据 保证 整个链式结构中不存在环。

注意,函数返回结果后,链表必须 保持其原始结构 。

自定义评测:

评测系统 的输入如下(你设计的程序 不适用 此输入):

    intersectVal - 相交的起始节点的值。如果不存在相交节点,这一值为 0
    listA - 第一个链表
    listB - 第二个链表
    skipA - 在 listA 中(从头节点开始)跳到交叉节点的节点数
    skipB - 在 listB 中(从头节点开始)跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构,并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 视作正确答案 。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/intersection-of-two-linked-lists
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(headA==nullptr || headB==nullptr)return nullptr;ListNode *l1 = headA, *l2 = headB;while(l1 != l2){l1 = l1==nullptr ? headB : l1->next;l2 = l2==nullptr ? headA : l2->next;}return l1;}
};

 141. 环形链表

给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ,则返回 true 。 否则,返回 false 。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

class Solution {
public:bool hasCycle(ListNode *head) {//if(head==nullptr || head->next==nullptr)return false;ListNode* fast = head;ListNode* slow = head;while(fast!=nullptr && fast->next!=nullptr){fast = fast->next->next;slow = slow->next;if(fast == slow) // 如果快慢指针相遇 则有环return true;}return false;}
};

 142. 环形链表 II

给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode *fast = head;ListNode *slow = head;bool flag = 0;while(fast!=nullptr && fast->next!=nullptr){fast = fast->next->next;slow = slow->next;if(slow == fast){flag = 1;   // 找到第一个相遇结点break;}}if(flag==0)return nullptr;ListNode *cur = head;    // 从head开始一起往后走while(cur != fast)      {cur = cur->next;    //再次相遇即为入环口fast = fast->next;}return cur;}
};

138. 复制带随机指针的链表

给你一个长度为 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 作为传入参数。

示例 1:

 【解法一】使用哈希表来存储旧结点与新结点之间的对印关系

class Solution {
public:Node* copyRandomList(Node* head) {if(head == nullptr) return nullptr;Node* newhead = new Node(0);newhead->next = nullptr;Node* cur = head, *pre = newhead;map<Node*, Node*> mp;while(cur){Node* node = new Node(cur->val);pre->next = node;mp[cur] = node;cur = cur->next;pre = pre->next;}for(auto &node : mp){if(node.first->random == nullptr)node.second->random = nullptr;elsenode.second->random = mp[node.first->random];}return newhead->next;}
};

【解法二】

/*
// 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 == nullptr) return nullptr;Node* cur = head;while(cur){Node* node = new Node(cur->val);node->next = cur->next;cur->next = node;cur = node->next;}for(cur = head; cur != nullptr; cur=cur->next->next){if(cur->random == nullptr)cur->next->random = nullptr;elsecur->next->random = cur->random->next;}cur = head->next;Node *pre = head, *newhead = head->next;while(cur->next){pre->next = pre->next->next;cur->next = cur->next->next;pre = pre->next;cur = cur->next;}pre->next = nullptr;return newhead;}
};

 

 

相关文章:

链表OJ(一)

目录 从尾到头打印链表_牛客题霸_牛客网 160. 相交链表 141. 环形链表 142. 环形链表 II 138. 复制带随机指针的链表 从尾到头打印链表_牛客题霸_牛客网 输入一个链表的头节点&#xff0c;按链表从尾到头的顺序返回每个节点的值&#xff08;用数组返回&#xff09;。 如输入…...

MySQL第三次作业

1、显示所有职工的基本信息。 2、查询所有职工所属部门的部门号&#xff0c;不显示重复的部门号。 3、求出所有职工的人数。 4、列出最高工和最低工资。 5、列出职工的平均工资和总工资。 6、创建一个只有职工号、姓名和参加工作的新表&#xff0c;名为工作日期表…...

Python中的类和对象(7)

1.私有变量 在大多数面向对象的编程语言中&#xff0c;都存在着私有变量&#xff08;private variable&#xff09;的概念&#xff0c;所谓私有变量&#xff0c;就是指通过某种手段&#xff0c;使得对象中的属性或方法无法被外部所访问。 Python 对于私有变量的实现是引入了一…...

【JVM】7种经典的垃圾收集器

文章目录1. 垃圾收集器概述2. Serial 收集器3. ParNew 收集器4. Paraller Scavenge 收集器5. Serial Old收集器6. Parller Old收集器7. CMS 收集器8. Garbage First 收集器本文参考&#xff1a;深入理解Java虚拟机&#xff1a;JVM高级特性与最佳实践&#xff08;第3版&#xff…...

2023/2/12总结

滑动窗口&#xff08;1&#xff09;滑动窗口是一种基于双指针的思想&#xff0c;两个指针指向的元素形成一个窗口。一般用于求取数组或字符串的某个子串、子序列、最长最短等最值或者求某个目标值时&#xff0c;并且该问题本身可以通过暴力解决。滑动窗口分为固定窗口和不定窗口…...

Linux之正则表达式

正则表达式是组成“操作”的基本语法&#xff0c;而这些“操作”是应用于Sed和Awk必备的能力。因此只有了解了正则表达式&#xff0c;才能学好Sed和Awk。正则表达式分为基础正则表达式&#xff08;Regular Expression&#xff09;与扩展正则表达式&#xff08;Extended Regular…...

前端高频面试题-HTML和CSS篇(一)

&#x1f4bb; 前端高频面试题-HTML和CSS篇&#xff08;一&#xff09; &#x1f3e0;专栏&#xff1a;前端面试题 &#x1f440;个人主页&#xff1a;繁星学编程&#x1f341; &#x1f9d1;个人简介&#xff1a;一个不断提高自我的平凡人&#x1f680; &#x1f50a;分享方向…...

Redis 专题总结

1. 什么是Redis &#xff1f; 处理&#xff1a;内容缓存&#xff0c;主要用于处理大量数据的高访问负载。Redis是一款高性能的NOSQL系列的非关系型数据库&#xff0c;NoSQL(NoSQL Not Only SQL)&#xff0c;意即“不仅仅是SQL”&#xff0c;是一项全新的数据库理念&#xff0…...

【Python百日进阶-Web开发-Vue3】Day515 - Vue+ts后台项目2:登录页面

文章目录 一、创建登录路由1.1 安装 Vue VSCode Snippets插件1.2 处理路径引用的红色波浪线1.3 入口文件 main.ts1.4 主组件 App.vue1.5 路由文件 router/index.ts1.6 首页组件 views/HomeView.vue1.7 登录组件 views/LoginView.vue二、实现登录页面的表单展示2.1 element-plus…...

【博客620】prometheus如何优化远程读写的性能

prometheus如何优化远程读写的性能 场景 为了解决prometheus本地存储带来的单点问题&#xff0c;我们一般在高可用监控架构中会使用远程存储&#xff0c;并通过配置prometheus的remote_write和remote_read来对接 远程写优化&#xff1a;remote_write 远程写的原理&#xff1a…...

redis可视工具AnotherRedisDesktopManager的使用

redis可视工具AnotherRedisDesktopManager的使用 简介 Another Redis DeskTop Manager 是一个开源项目&#xff0c;提供了以可视化的方式管理 Redis 的功能&#xff0c;可供免费下载安装&#xff0c;也可以在此基础上进行二次开发&#xff0c;主要特点有&#xff1a; 支持 W…...

【idea】idea生产类注释和方法注释

网上有很多类似的文章&#xff0c;但是我在按照他们的文章设置后&#xff0c;出现了一些问题&#xff0c;因此我这边在解决了问题后&#xff0c;总结一篇文章&#xff0c;发出来给大家借鉴一下。在此先说明一下idea的版本&#xff0c;是2020.1.3 设置动态模板&#xff0c;File…...

jenkins +docker+python接口自动化之jenkins容器安装python3(二)

jenkins dockerpython接口自动化之jenkins容器安装python3&#xff08;二&#xff09; 目录&#xff1a;导读 前提是在docker下已经配置好jenkins容器了&#xff0c;是将python安装在jenkins容器下的 1、先看你的jenkins是否安装好 2、以root权限进入jenkins容器&#xff1…...

go 命令行工具整理

这里会整理可能会使用到的命令行参数&#xff0c;比如 go build、go run&#xff0c;诸如此类。了解这些内容对我们工作会有什么帮助吗&#xff1f;更多的时候&#xff0c;是能让我们理解代码编译的意图&#xff0c;或者&#xff0c;给我们一种排查问题的手段。 比方说&#x…...

RuntimeError: CUDA out of memory

今天在训练模型的时候突然报了显存不够的问题&#xff0c;然后分析了一下&#xff0c;找到了解决的办法&#xff0c;这里记录一下&#xff0c;方便以后查阅。 注&#xff1a;以下的解决方案是在模型测试而不是模型训练时出现这个报错的&#xff01; RuntimeError: CUDA out of…...

Kubernetes1.25中Redis集群部署实例

1、概述我们知道在 Kubernetes 容器编排平台中, 我们可以非常方便的进行应用的扩容缩, 同时也能非常方便的进行业务的迭代&#xff0c;本章主要讲解在Kubernetes1.25搭建Redis单实例和Redis集群主从同步的环境流程步骤, 如果是高频访问重要的线上业务我们最好是部署在物理机器上…...

C++11实现计算机网络中的TCP/IP连接(Windows端)

目录引言1、TCP2、IP2.1 IP路由器3、TCP/IP4、TCP/IP协议C11实现参考文献引言 TCP/IP 指传输控制协议/网际协议&#xff08;Transmission Control Protocol / Internet Protocol&#xff09;。[1] 在TCP/IP协议簇中主要包含以下内容&#xff1a; TCP (传输控制协议) - 应用程序…...

Spring框架自定义实现IOC基础功能/IDEA如何手动实现IOC功能

继续整理记录这段时间来的收获&#xff0c;详细代码可在我的Gitee仓库Java设计模式克隆下载学习使用&#xff01; 7.4 自定义Spring IOC 创建新模块&#xff0c;结构如图![[Pasted image 20230210173222.png]] 7.4.1 定义bean相关POJO类 7.4.1.1 定义propertyValue类 /** …...

pip离线安装windows版torch

文章目录前言conda创建虚拟环境安装torchtorch官网在线安装离线手动安装测试是否安装成功后记前言 学习的时候遇到几个机器学习相关的项目&#xff0c;由于不同的项目之间用到的依赖库不太一样&#xff0c;于是想利用conda为不同的项目创建不同的环境方便管理和运行&#xff0…...

Redis核心知识点

Redis核心知识点Redis核心知识点大全五种数据类型redis整合SpringBoot序列化问题渐进式扫描慢查询缓存相关问题数据库和缓存谁先更新缓存穿透缓存雪崩缓存击穿实际应用超卖问题分布式锁全局唯一ID充当消息队列Feed流附近商户签到HyperLogLog实现UV统计持久化RDBAOF持久化小结事…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...