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

相交链表(Leetcode)

 题目分析:

. - 力扣(LeetCode)

相交链表:首先我想到的第一个思路是:如图可知,A和B链表存在长度差,从左边一起遍历链表不好找交点,那我们就从后面开始找,但是这是单链表,没有 prev 指针,所以只能反转链表 A、B。反转之后再从A、B头结点开始就可以找到相遇点,但是题目要求我们不能改变链表的结构,所以此方法不行。

方法一:

思路:

 ①当链表有一个为空,或者两个都为空的时候,直接返回NULL。

 ②因为链表存在差值,结点个数不同,不能一起遍历,所以我们可以求出A和B各自的结点个数,然后求出差值。

③差值有了之后,我们可以让长的链表先走差值步,相对于抹掉了差值。

④最后A、B链表一起走,如果地址相等就表示相遇了,就返回交点处的地址,如果没有相遇,就返回NULL

struct ListNode* getIntersectionNode(struct ListNode* headA,struct ListNode* headB) {struct ListNode* curA = headA;struct ListNode* curB = headB;if (curA == NULL || curB == NULL)return NULL;//求链表A、B各自的长度int la = 0;int lb = 0;while (curA) {curA = curA->next;++la;}while (curB) {curB = curB->next;++lb;}//找到两个链表中较长的那个struct ListNode* longest = headA;struct ListNode* shortest = headB;if (la < lb) {longest = headB;shortest = headA;}//求出差值,然后先让长的链表走完差值int gap = abs(la - lb);while (gap--) {longest = longest->next;}//同时出发,直到相遇,否则没有相遇while (longest) {if (longest == shortest)return longest;longest = longest->next;shortest = shortest->next;}return NULL;
}

 

方法二:

思路:

①当链表有一个为空,或者两个都为空的时候,直接返回NULL。

②相当于两个指针在一个路线上走、走的路程都是一样的

A先走完自己的路程,然后去走B的路程

B先走完自己的路程,然后去走A的路程

A和B走到路一样长

如果存在相遇点,A和B必定会相遇 (如果不是很明白可以对着代码,画图去理解一下)

如果不存在相遇点,就在NULL处相遇

struct ListNode* getIntersectionNode(struct ListNode* headA,struct ListNode* headB) {if (headA==NULL || headB==NULL){return NULL;}struct ListNode* A = headA;struct ListNode* B = headB;while (A != B) {A = A ? A->next : headB; B = B ? B->next : headA;}return A;
}

 

相关文章:

相交链表(Leetcode)

题目分析&#xff1a; . - 力扣&#xff08;LeetCode&#xff09; 相交链表&#xff1a;首先我想到的第一个思路是&#xff1a;如图可知&#xff0c;A和B链表存在长度差&#xff0c;从左边一起遍历链表不好找交点&#xff0c;那我们就从后面开始找&#xff0c;但是这是单链表&…...

建造者模式(大话设计模式)C/C++版本

建造者模式 C 参考&#xff1a;https://www.cnblogs.com/Galesaur-wcy/p/15907863.html #include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std;// Product Class&#xff0c;产品类&#xff0c;由多个…...

【地质灾害监测实现有效预警,44人提前安全转移】

6月13日14时&#xff0c;国信华源地质灾害监测预警系统提前精准预警&#xff0c;安全转移10户44人。 该滑坡隐患点通过科学部署国信华源裂缝计、倾角加速度计、雨量计、预警广播等自动化、智能化监测预警设备&#xff0c;实现了对隐患点裂缝、位移、降雨量等关键要素的实时动态…...

Ruby 数据库访问 - DBI 教程

Ruby 数据库访问 - DBI 教程 本文将详细介绍如何使用 Ruby 的 DBI(Database Interface)库来访问和操作数据库。DBI 是 Ruby 语言中一个常用的数据库接口库,它提供了一套统一的接口来访问不同的数据库系统,如 MySQL、PostgreSQL、SQLite 等。通过本文的学习,您将掌握如何使…...

Linux环境搭建之CentOS7(包含静态IP配置)

&#x1f525; 本文由 程序喵正在路上 原创&#xff0c;CSDN首发&#xff01; &#x1f496; 系列专栏&#xff1a;虚拟机 &#x1f320; 首发时间&#xff1a;2024年6月22日 &#x1f98b; 欢迎关注&#x1f5b1;点赞&#x1f44d;收藏&#x1f31f;留言&#x1f43e; 安装VMw…...

Dell戴尔灵越Inspiron 16 Plus 7640/7630笔记本电脑原装Windows11下载,恢复出厂开箱状态预装OEM系统

灵越16P-7630系统包: 链接&#xff1a;https://pan.baidu.com/s/1Rve5_PF1VO8kAKnAQwP22g?pwdjyqq 提取码&#xff1a;jyqq 灵越16P-7640系统包: 链接&#xff1a;https://pan.baidu.com/s/1B8LeIEKM8IF1xbpMVjy3qg?pwdy9qj 提取码&#xff1a;y9qj 戴尔原装WIN11系…...

.NET C# 装箱与拆箱

.NET C# 装箱与拆箱 目录 .NET C# 装箱与拆箱1 装箱 (Boxing)1.1 过程&#xff1a;1.2 示例&#xff1a; 2 拆箱 (Unboxing)2.1 过程&#xff1a;2.2 示例&#xff1a; 3 性能影响4 性能优化4.1 使用泛型集合示例&#xff1a; 4.2 使用Nullable<T>示例&#xff1a; 4.3 避…...

springboot与flowable(9):候选人组

act_id_xxx相关表存储了所有用户和组的数据。 一、维护用户信息 Autowiredprivate IdentityService identityService;/*** 维护用户*/Testvoid createUser() {User user identityService.newUser("zhangsan");user.setEmail("zhangsanqq.com");user.setF…...

为什么要选择华为 HCIE-Security 课程?

2020 年我国网络安全市场规模达到 680 亿元&#xff0c;同比增长 25%。随着对网络安全的愈加重视及布局&#xff0c;市场规模将持续扩大。 近年来&#xff0c;随着“云大物工移智”等新兴技术的快速发展和普及应用&#xff0c;数字化已经融入社会经济生活的方方面面&#xff0c…...

C++之std::queue::emplace

std::queue::emplace 是 C STL 中 std::queue 容器的成员函数&#xff0c;它用于在队列的末尾就地构造一个新元素。这个函数类似于 std::queue::push&#xff0c;但是 emplace 允许你通过传递参数来构造元素&#xff0c;而不需要显式地创建一个元素对象。 理解 std::queue::em…...

Vue3 - 在项目中使用vue-i18n不生效的问题

检查和配置 Vue I18n 确保你已经正确安装了Vue I18n并且配置了组合API模式。 安装 Vue I18n npm install vue-i18nnext配置 i18n.js import { createI18n } from vue-i18n; import messages from ./messages;const i18n createI18n({legacy: false, // 使用组合 API 模式l…...

Day 44 Ansible自动化运维

Ansible自动化运维 几种常用运维工具比较 ​ Puppet ​ —基于 Ruby 开发,采用 C/S 架构,扩展性强,基于 SSL,远程命令执行相对较弱ruby ​ SaltStack ​ —基于 Python 开发,采用 C/S 架构,相对 puppet 更轻量级,配置语法使用 YAML,使得配置脚本更简单 ​ Ansible ​ —基于 …...

Excel/WPS《超级处理器》功能介绍与安装下载

超级处理器是基于Excel或WPS开发的一款插件&#xff0c;拥有近300个功能&#xff0c;非常简单高效的处理表格数据&#xff0c;安装即可使用。 点击此处&#xff1a;超i处理器安装下载 Excel菜单&#xff0c;显示如下图所示&#xff1a; WPS菜单显示&#xff0c;如下图所示&am…...

U-Net for Image Segmentation

1.Unet for Image Segmentation 笔记来源&#xff1a;使用Pytorch搭建U-Net网络并基于DRIVE数据集训练(语义分割) 1.1 DoubleConv (Conv2dBatchNorm2dReLU) import torch import torch.nn as nn import torch.nn.functional as F# nn.Sequential 按照类定义的顺序去执行模型&…...

POI导入带有合并单元格的excel,demo实例,直接可以运行

直接可以运行 import org.apache.poi.hssf.usermodel.HSSFWorkbook; import org.apache.poi.ss.usermodel.Cell; import org.apache.poi.ss.usermodel.Row; import org.apache.poi.ss.usermodel.Sheet; import org.apache.poi.ss.usermodel.Workbook; import org.apache.poi.s…...

【C语言】解决C语言报错:Use-After-Free

文章目录 简介什么是Use-After-FreeUse-After-Free的常见原因如何检测和调试Use-After-Free解决Use-After-Free的最佳实践详细实例解析示例1&#xff1a;释放内存后未将指针置为NULL示例2&#xff1a;多次释放同一指针示例3&#xff1a;全局或静态指针被释放后继续使用示例4&am…...

C语言经典例题-19

1.字符串左旋结果 题目内容&#xff1a;写一个函数&#xff0c;判断一个字符串是否为另外一个字符串旋转之后的字符串。 例&#xff1a;给定s1 AABCD和s2 BCDAA,返回1 给定s1 abcd和s2 ACBD,返回0 AABCD左旋一个字符得到ABCDA AABCD左旋两个字符得到BCDAA AABCD右旋一…...

AlmaLinux 更换CN镜像地址

官方镜像列表 官方列表&#xff1a;https://mirrors.almalinux.org/CN 开头的站点&#xff0c;不同区域查询即可 一键更改镜像地址脚本 以下是更改从默认更改到阿里云地址 cat <<EOF>>/AlmaLinux_Update_repo.sh #!/bin/bash # -*- coding: utf-8 -*- # Author:…...

【笔记】【矩阵的二分】668. 乘法表中第k小的数

力扣链接&#xff1a;题目 参考地址&#xff1a;参考 思路&#xff1a;二分查找 把矩阵想象成一维的已排好序的数组&#xff0c;用二分法找第k小的数字。 假设m行n列&#xff0c;则对应一维下标范围是从1到mn&#xff0c;初始&#xff1a; l1; rmn; mid(lr)/2 设mid在第i行&a…...

红米手机RedNot11无法使用谷歌框架,打开游戏闪退的问题,红米手机如何开启谷歌框架

红米手机RedNot11无法使用谷歌框架&#xff0c;打开游戏闪退的问题&#xff0c; 1.问题描述2.问题原因3.解决方案3.1配置谷歌框架&#xff1a;3.1软件优化 4.附图 1.问题描述 红米手机打开安卓APP没有广告&#xff0c;直接闪退&#xff0c;无法使用谷歌框架 异常关键词中包含&…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

spring Security对RBAC及其ABAC的支持使用

RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型&#xff0c;它将权限分配给角色&#xff0c;再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...

jdbc查询mysql数据库时,出现id顺序错误的情况

我在repository中的查询语句如下所示&#xff0c;即传入一个List<intager>的数据&#xff0c;返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致&#xff0c;会导致返回的id是从小到大排列的&#xff0c;但我不希望这样。 Query("SELECT NEW com…...

基于开源AI智能名片链动2 + 1模式S2B2C商城小程序的沉浸式体验营销研究

摘要&#xff1a;在消费市场竞争日益激烈的当下&#xff0c;传统体验营销方式存在诸多局限。本文聚焦开源AI智能名片链动2 1模式S2B2C商城小程序&#xff0c;探讨其在沉浸式体验营销中的应用。通过对比传统品鉴、工厂参观等初级体验方式&#xff0c;分析沉浸式体验的优势与价值…...