【数据结构OJ题】相交链表

原题链接:https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

目录

1. 题目描述

2. 思路分析

3. 代码实现


1. 题目描述

 

2. 思路分析

看到这道题,很容易想到的方法就是暴力求解,就是将一个链表的每个结点的地址分别和另外一个链表的每个结点的地址进行比较,如果有相等的,就说明相交了。(注意这里不能比值,因为两个不同的结点值有可能一样)。但是这样的时间复杂度太高了,为O(N^2)。

这道题有一个很好的做法:

先计算出两个链表的长度,让长的链表先走相差的长度,然后两个链表同时走,直到遇到相同的结点,即为第一个公共结点

我们定义了四个变量curA,curB,lenA,lenB。

我们用结构体指针curA遍历链表A,用结构体指针curB遍历链表B

lenA表示链表A的长度lenB表示链表B的长度

用while循环通过遍历分别得到了链表A和B的长度。

我们判断尾结点是否相等,如果尾结点相等,说明两个链表一定相交!!!

(我们看下图,如果两个链表相交,那么从这个相交的结点(包括这个交点)之后的结点,在两个链表中都是相等的。所以尾结点相等,说明两个链表一定相交。)

如果两个链表不相交curA!=curB),我们直接返回空指针NULL

如果两个链表相交,我们先让长的链表走两个链表长度的差距步(gap)。因为不知道两个链表哪个长,所以我们使用了abs()函数,差距步gap就是abs(lenA-lenB)。

之后我们又引入了两个结构体指针longListshortList分别指向长链表短链表的头。这里用了if语句判断先假设某个链表是长链表,如果不是,就让它等于短链表

然后我们用一个while循环让长链表走差距步while(gap--))。

然后让longList和shortList这两个结构体指针同时走找交点,找到交点时结束循环。

最后返回longList即可。

3. 代码实现

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode *curA=headA,*curB=headB;int lenA=1,lenB=1;//计算链表长度while(curA->next){curA=curA->next;  ++lenA;}while(curB->next){curB=curB->next;++lenB;}//不相交if(curA!=curB)return NULL;int gap=abs(lenA-lenB);struct ListNode *longList=headA,*shortList=headB;if(lenA<lenB){longList=headB;shortList=headA;}//长的先走差距步while(gap--){longList=longList->next;}//同时走找交点while(longList!=shortList){longList=longList->next;shortList=shortList->next;}return longList;
}

 

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

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

相关文章

曲线救国 | 双非渣硕的秋招路

作者 | 带带大兄弟 面试锦囊之面经分享系列&#xff0c;持续更新中 欢迎后台回复"面试"加入讨论组交流噢 一篇旧文&#xff0c;可以参考~ 写在前面 双非渣硕&#xff0c;0实习&#xff0c;3篇水文&#xff0c;三个给老板当打工仔的nlp横向项目&#xff0c;八月份开…

文本三剑客之sed编辑器

sed 一、sed简介1.1 什么是sed&#xff1f;1.2 sed原理1.3 sed核心功能 二、sed命令格式详解2.1 命令格式2.2 常用选项2.3 sed脚本语法2.3.1 基本语法结构2.3.2 地址部分-----指定匹配范围2.3.3 命令部分-----要执行的命令 三、sed查找替换3.1 基本语法3.2 分组后向引用3.3 变量…

【面试八股文】每日一题:谈谈你对线程的理解

每日一题-Java核心-谈谈你对线程的理解【面试八股文】 Java线程是Java程序中的执行单元。一个Java程序可以同时运行多个线程&#xff0c;每个线程可以独立执行不同的任务。线程的执行是并发的&#xff0c;即多个线程可以同时执行。 1. 线程的特点 Java中的线程有如下的特点 轻…

[LeetCode - Python]844. 比较;含退格的字符串(Easy);415. 字符串相加(Easy)

1.题目 844. 比较含退格的字符串&#xff08;Easy&#xff09; 1.代码&#xff1a; class Solution:def backspaceCompare(self, s: str, t: str) -> bool:# 暴力法s list(s)t list(t)M 0N 0for i in range(len(s)):i -M if s[i] # :if i > 0 :s.pop(i)s.pop(i-…

LION AI 大模型落地,首搭星纪元 ES

自新能源汽车蓬勃发展以来&#xff0c;随着潮流不断进步和变革的“四大件”有着明显变化。其中有&#xff1a;平台、智能驾驶、配置、以及车机。方方面面都有着不同程度的革新。 而车机方面&#xff0c;从以前老旧的媒体机、 CD 机发展至如今具有拓展性、开放性、智能化的车机…

Docker部署php运行环境(php-fpm+nginx)

前言 如果使用docker去部署一套php的运行环境&#xff0c;我们需要构建出nginx、php-fpm两个容器&#xff0c;nginx通过fast_cgi协议去转发php-fpm中的端口&#xff0c;从而实现web server的搭建&#xff0c;接下来以php的laravel框架为演示例子。 部署php-fpm 第一步 编写ph…

一、数学建模之线性规划篇

1.定义 2.例题 3.使用软件及解题 一、定义 1.线性规划&#xff08;Linear Programming&#xff0c;简称LP&#xff09;是一种数学优化技术&#xff0c;线性规划作为运筹学的一个重要分支&#xff0c;专门研究在给定一组线性约束条件下&#xff0c;如何找到一个最优的决策&…

Prometheus 监控系统---你值得拥有

目录 一&#xff1a;Prometheus 1、Prometheus 概述 2、应用场景 3、Prometheus 的特点 4、Prometheus 的生态组件 &#xff08;1&#xff09;Prometheus server&#xff1a;服务核心组件 &#xff08;2&#xff09;Client Library: 客户端库 &#xff08;3&#xff0…

前端开发怎么解决前端安全性的问题? - 易智编译EaseEditing

前端安全性是保护前端应用程序免受恶意攻击和数据泄露的重要方面。以下是一些解决前端安全性问题的关键方法&#xff1a; 输入验证与过滤&#xff1a; 对所有用户输入进行验证和过滤&#xff0c;防止恶意用户通过注入攻击等手段破坏应用程序或获取敏感信息。 跨站点脚本&#…

安卓移动应用开发实训室建设方案

一 、系统概述 安卓移动应用开发作为新一代信息技术的重点和促进信息消费的核心产业&#xff0c;已成为我国转变信息服务业的发展新热点&#xff1a;成为信息通信领域发展最快、市场潜力最大的业务领域。互联网尤其是移动互联网&#xff0c;以其巨大的信息交换能力和快速渗透能…

k8s 自身原理之高可用

说到高可用&#xff0c;咱们在使用主机环境的时候&#xff08;非 k8s&#xff09;&#xff0c;咱做高可用有使用过这样的方式&#xff1a; 服务器做主备部署&#xff0c;当主节点和备节点同时存活的时候&#xff0c;只有主节点对外提供服务&#xff0c;备节点就等着主节点挂了…

logstash配置文件

input { kafka { topics > “xxxx” bootstrap_servers > “ip:port” auto_offset_reset > “xxxx” group_id > “xxxx” consumer_threads > 3 codec > “json” } } filter { grok { match > { “message” > ‘%{IP:client_ip} - - [%{HTTPDATE:…

PostgreSQL父子建表查询所有的子数据-利用自定义函数查询

pgsql 函数查询代码 select find_space_tree_list_by_nodeid(1,1) 查询结果示意图 获取子集函数代码 CREATE OR REPLACE FUNCTION "public"."find_space_tree_list_by_nodeid"("nodeid" varchar, "viewid" varchar)RETURNS "…

电脑远程接入软件可以进行文件传输吗?快解析内网穿透

电脑远程接入软件的出现&#xff0c;让我们可以在两台电脑之间进行交互和操作。但是&#xff0c;很多人对于这些软件能否进行文件传输还存在一些疑问。下面的文章将解答这个问题。 1.电脑远程接入软件可以进行文件传输。传统上&#xff0c;我们可能会通过传输线或者移动存储设…

【图论】Floyd算法

一.简介 Floyd算法&#xff0c;也称为Floyd-Warshall算法&#xff0c;是一种用于解决所有节点对最短路径问题的动态规划算法。它可以在有向图或带权图中找到任意两个节点之间的最短路径。 Floyd算法的基本思想是通过中间节点逐步优化路径长度。它使用一个二维数组来存储任意两…

mongodb 数据库管理(数据库、集合、文档)

目录 一、数据库操作 1、创建数据库 2、删除数据库 二、集合操作 1、创建集合 2、删除集合 三、文档操作 1、创建文档 2、 插入文档 3、查看文档 4、更新文档 1&#xff09;update() 方法 2&#xff09;replace() 方法 一、数据库操作 1、创建数据库 创建数据库…

钛合金为何成为iPhone 15 Pro材料首选?

多年来&#xff0c;iPhone Pro一直采用厚重的钢框架&#xff0c;但不会持续太久。 有了iPhone 15 Pro&#xff0c;苹果可能会从钢框架转向钛框架&#xff0c;这不仅仅是因为它听起来更酷。钛比钢有很多优点&#xff0c;尤其是它更轻&#xff0c;这将解决iPhone Pro与普通iPhon…

Python爬虫——scrapy_日志信息以及日志级别

日志级别&#xff08;由高到低&#xff09; CRITICAL&#xff1a; 严重错误 ERROR&#xff1a; 一般错误 WARNING&#xff1a; 警告 INFO&#xff1a; 一般警告 DEBUG&#xff1a; 调试信息 默认的日志等级是DEBUG 只要出现了DEBUG或者DEBUG以上等级的日志&#xff0c;那么这些…

哪些人适合参加大数据培训班?

互联网加速职场变革&#xff0c;大数据浪潮席卷全球。日前&#xff0c;Python、大数据、人工智能是当今最热门的话题。大数据存储、大数据分析、 人工智能等开发人才需求旺盛。 大数据培训班有大数据分析培训班、大数据开发培训班&#xff0c;JAVA培训班 大数据班适学人群…