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

【Leedcode】数据结构中链表必备的面试题(第四期)

【Leedcode】数据结构中链表必备的面试题(第四期)


文章目录

  • 【Leedcode】数据结构中链表必备的面试题(第四期)
    • 1.题目
    • 2.思路+图解
    • (1)思路一
    • (2)思路二
    • 3.源代码
  • 总结


1.题目

  1. 相交链表: 如下(示例):
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。
图示两个链表在节点 c1 开始相交:题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。

1.判断两个链表是否相交? 2.如果相交,求交点


在这里插入图片描述


在这里插入图片描述


在这里插入图片描述


2.思路+图解

(1)思路一

暴力求解-穷举法。依次取A链表中的每个节点跟B链表中的所有结点比较。
如果有相同的结点,就是相交,第一个相同的交点就是公共结点。这样做的时间复杂度为:O(N^2)
那么我们如何把时间复杂度优化到:O(N)


(2)思路二

1.尾结点相同就是相交,否则就不相交
2.求交点:长的链表先走(长度差)步,再同时走,第一个相同的结点就是交点
具体如下图


在这里插入图片描述


再这里要注意:可以用lenA和lenB去算两个链表的长度,方便求交点位置,如下图
在这里插入图片描述


在这里插入图片描述


在这里插入图片描述


3.源代码

代码如下(示例):

struct ListNode 
{int val;struct ListNode *next;
};
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode* pheadA = headA;struct ListNode* pheadB = headB;//先判断是否为环形结构int lenA = 1;while(pheadA -> next){lenA++;pheadA = pheadA -> next;}int lenB = 1;while(pheadB -> next){lenB++;pheadB = pheadB -> next;}if(pheadA != pheadB){return NULL;}int sub = abs(lenA - lenB);struct ListNode* longlist = headA;struct ListNode* shortlist = headB;if(lenA < lenB){longlist = headB;shortlist = headA;}//长的先走sub步while(sub--){longlist = longlist -> next;}//俩个开始一起走while(longlist != shortlist){longlist = longlist -> next;shortlist = shortlist -> next;}return longlist;
}

总结

以上就是今天要讲的内容,本文介绍数据结构中链表必备的面试题(第四期)
如果我的博客对你有所帮助记得三连支持一下,感谢大家的支持!
在这里插入图片描述

相关文章:

【Leedcode】数据结构中链表必备的面试题(第四期)

【Leedcode】数据结构中链表必备的面试题&#xff08;第四期&#xff09; 文章目录【Leedcode】数据结构中链表必备的面试题&#xff08;第四期&#xff09;1.题目2.思路图解(1)思路一(2)思路二3.源代码总结1.题目 相交链表&#xff1a; 如下&#xff08;示例&#xff09;&…...

【2023】助力Android金三银四面试

前言 新气象&#xff0c;新生机。在2023年的Android开发行业中&#xff0c;又有那些新的面试题出现呢&#xff1f;对于Android面试官的拷问&#xff0c;我们又如何正确去解答&#xff1f;万变不离其宗&#xff0c;其实只要Android的技术层面没变化&#xff0c;面试题也就是差不…...

Leetcode.1801 积压订单中的订单总数

题目链接 Leetcode.1801 积压订单中的订单总数 Rating &#xff1a; 1711 题目描述 给你一个二维整数数组 orders&#xff0c;其中每个 orders[i] [pricei, amounti, orderTypei]表示有 amounti笔类型为 orderTypei、价格为 pricei的订单。 订单类型 orderTypei 可以分为两种…...

红帽Linux技术-cp命令

cp是一个复制文件或者目录的命令&#xff0c;其作用是将一个或多个文件或目录从源位置复制到目标位置。 格式&#xff1a;cp [选项] 源文件或目录 目标文件或目录 常用选项&#xff1a; -r&#xff1a;复制目录及其子目录下的所有文件和目录&#xff1b; -p&#xff1a;保留…...

代码随想录算法训练营day41 | 动态规划 01背包问题基础 01背包问题之滚动数组

01背包问题基础 问题描述 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]&#xff0c;得到的价值是value[i] 。每件物品只能用一次&#xff0c;求解将哪些物品装入背包里物品价值总和最大。 举个栗子 背包最大重量为4。 物品为&#xff1a; 重量价值…...

MyBatis学习笔记(三) —— MyBatis核心配置文件详解

3、核心配置文件详解 id是唯一标识&#xff0c;不能重复&#xff0c;但是在真正开发过程中&#xff0c;不可能一个项目中同时使用两个环境&#xff0c;肯定会使用其中的某一个&#xff0c;这时候它的default就比较重要了。 default是设置我们当前使用的默认环境的id <?x…...

使用GDAL进行坐标转换

1、地理坐标系与投影坐标系空间参考中主要包含大地水准面、地球椭球体、投影坐标系等几部分内容。地图投影就是把地球表面的任意点&#xff0c;利用一定数学法则&#xff0c;转换到地图平面上的理论和方法&#xff0c;一般有两种坐标系来进行表示&#xff0c;分别是地理坐标系和…...

日常编程中和日期相关的代码和bug

本文主要是Java中和日期时间相隔的几个常用代码函数代码&#xff0c;做了总结&#xff0c;希望在日常编码中&#xff0c;可以帮到大家。 1.计算闰年 记住一个短语&#xff0c;“四年一润&#xff0c;百年不闰&#xff0c;四百再润”&#xff0c;不管换啥语言&#xff0c;相信…...

ATT与Intel汇编语法区别

寄存器、变量&#xff08;常量&#xff09;与立即数 在Intel汇编中&#xff0c;无论是寄存器、变量&#xff08;常量&#xff09;还是立即数&#xff0c;都是直接使用的&#xff0c;例如下列例子中分别加载一个变量&#xff08;常量&#xff09;与立即数到寄存器中&#xff1a…...

Spring Cloud Alibaba全家桶(一)——Spring Cloud Alibaba介绍

前言 本文为 Spring Cloud Alibaba介绍 相关知识&#xff0c;下边将对微服务介绍&#xff08;包括&#xff1a;系统架构演变、微服务架构介绍、常见微服务架构&#xff09;&#xff0c;Spring Cloud Alibaba介绍&#xff08;包括&#xff1a;Spring Cloud Alibaba 的定位、Spri…...

2023年网红营销10大趋势解读:品牌出海必看

前不久influencermarketinghub发布了《2023年影响者营销基准报告》&#xff0c;报告总结了3500多家营销机构、品牌和其他相关专业人士对当前网红营销现状的看法&#xff0c;以及预测了未来网红营销的一个发展趋势。本期Nox聚星就带领大家详细解读关于2023年网红营销的10大趋势。…...

Java学习笔记 --- 正则表达式

一、体验正则表达式 package com.javase.regexp;import java.util.regex.Matcher; import java.util.regex.Pattern;/*** 体验正则表达式&#xff0c;给文本处理带来哪些便利*/ public class Regexp_ {public static void main(String[] args) {//假设&#xff0c;编写了爬虫&…...

【基础算法】字符串哈希

&#x1f339;作者:云小逸 &#x1f4dd;个人主页:云小逸的主页 &#x1f4dd;Github:云小逸的Github &#x1f91f;motto:要敢于一个人默默的面对自己&#xff0c;强大自己才是核心。不要等到什么都没有了&#xff0c;才下定决心去做。种一颗树&#xff0c;最好的时间是十年前…...

unity 多个模型或物体无限循环拖拽 类似无限列表循环

using System.Collections; using System.Collections.Generic; using UnityEngine; public class ModelAnimal : MonoBehaviour { //需滑动的物体 public GameObject m_objA; //音乐 public GameObject m_objB; //电话 public GameObject m_objC; //导航 public GameObject m…...

GroupDocs.Merger for Java

GroupDocs.Merger for Java GroupDocs.Merger for Java是一个文档操作API&#xff0c;可帮助您合并、拆分、交换或删除文档页面。API通过启用或禁用密码提供保护&#xff0c;并允许开发人员加入PDF、Microsoft Word、Excel和Powerpoint文档。 支持的文件格式 Microsoft Office格…...

04--WXML

1、什么是WXML什么是Wxml呢&#xff1f;我们首先要介绍一下Html&#xff0c;Html的全称为HyperTextMarkup Language&#xff0c;翻译过来就是超文本标记语言&#xff0c;这种语言目前已经普遍用于前端开发&#xff0c;而wxml正是从html演变而来&#xff0c;它基于微信这个平台&…...

一篇五分生信临床模型预测文章代码复现——FIgure 9.列线图构建,ROC分析,DCA分析 (五)

之前讲过临床模型预测的专栏,但那只是基础版本,下面我们以自噬相关基因为例子,模仿一篇五分文章,将图和代码复现出来,学会本专栏课程,可以具备发一篇五分左右文章的水平: 本专栏目录如下: Figure 1:差异表达基因及预后基因筛选(图片仅供参考) Figure 2. 生存分析,…...

每月一书(202302)《狂飙》

文章目录剧情内容观看收获正菜很硬配菜很足食物还有喻义又到了每月一书的时间&#xff0c;本月没有阅读书籍&#xff0c;不过看了一部叫《狂飙》的电视剧&#xff0c;因为该电视剧热度高&#xff0c;所以我也凑个热闹。下面分享一下我看完后的体会。 剧情内容 这是一部扫黑和…...

wsl2 docker 安装

一. 更换镜像源 备份默认源&#xff1a; cp /etc/apt/sources.list /etc/apt/sourses.list.bak 编辑文件&#xff1a; vim /etc/apt/sources.list 删除原有内容并替换为&#xff1a; # 默认注释了源码镜像以提高 apt update 速度&#xff0c;如有需要可自行取消注释 deb …...

极光笔记 | 埋点体系建设与实施方法论

PART 01 前 言随着网络技术的发展&#xff0c;从粗犷型到精细化运营型&#xff0c;再到现在的数字化运营&#xff0c;数据变得越来越细分和重要&#xff0c;不仅可以进行策略调整&#xff0c;还可以实现自动化的精细化运营。而数据价值的起点就是埋点&#xff0c;只有合理地埋点…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

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

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

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

Springboot社区养老保险系统小程序

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

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...