当前位置: 首页 > 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;只有合理地埋点…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

WEB3全栈开发——面试专业技能点P4数据库

一、mysql2 原生驱动及其连接机制 概念介绍 mysql2 是 Node.js 环境中广泛使用的 MySQL 客户端库&#xff0c;基于 mysql 库改进而来&#xff0c;具有更好的性能、Promise 支持、流式查询、二进制数据处理能力等。 主要特点&#xff1a; 支持 Promise / async-await&#xf…...

用鸿蒙HarmonyOS5实现国际象棋小游戏的过程

下面是一个基于鸿蒙OS (HarmonyOS) 的国际象棋小游戏的完整实现代码&#xff0c;使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├── …...

Linux 内存管理调试分析:ftrace、perf、crash 的系统化使用

Linux 内存管理调试分析&#xff1a;ftrace、perf、crash 的系统化使用 Linux 内核内存管理是构成整个内核性能和系统稳定性的基础&#xff0c;但这一子系统结构复杂&#xff0c;常常有设置失败、性能展示不良、OOM 杀进程等问题。要分析这些问题&#xff0c;需要一套工具化、…...

uni-app学习笔记二十七--设置底部菜单TabBar的样式

官方文档地址&#xff1a;uni.setTabBarItem(OBJECT) | uni-app官网 uni.setTabBarItem(OBJECT) 动态设置 tabBar 某一项的内容&#xff0c;通常写在项目的App.vue的onLaunch方法中&#xff0c;用于项目启动时立即执行 重要参数&#xff1a; indexnumber是tabBar 的哪一项&…...

边缘计算设备全解析:边缘盒子在各大行业的落地应用场景

随着工业物联网、AI、5G的发展&#xff0c;数据量呈爆炸式增长。但你有没有想过&#xff0c;我们生成的数据&#xff0c;真的都要发回云端处理吗&#xff1f;其实不一定。特别是在一些对响应时间、网络带宽、数据隐私要求高的行业里&#xff0c;边缘计算开始“火”了起来&#…...