leetcode160. 相交链表

news/2024/4/24 23:00:50/

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

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

在这里插入图片描述
题目数据 保证 整个链式结构中不存在环。

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

自定义评测:

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

intersectVal - 相交的起始节点的值。如果不存在相交节点,这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中(从头节点开始)跳到交叉节点的节点数
skipB - 在 listB 中(从头节点开始)跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构,并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 视作正确答案 。

示例 1:

在这里插入图片描述
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出:Intersected at ‘8’
解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,6,1,8,4,5]。
在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
— 请注意相交节点的值不为 1,因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说,它们在内存中指向两个不同的位置,而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点,B 中第四个节点) 在内存中指向相同的位置。

思路:
两个指针分别指向两个链表表头,依次遍历判断两个指针指向的结点是否相等,若一方结点走到末尾为空后,指向另一个链表的头结点接着遍历比较,经过数学分析最多遍历m+n次,即可获得相交结点或者不存在相交结点。

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;struct ListNode {int val;ListNode* next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode* next) : val(x), next(next) {}
};
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {if (headA == nullptr || headB == nullptr)return nullptr;ListNode* pa = headA;ListNode* pb = headB;while (pa != nullptr || pb != nullptr)//走的次数一样 所以最后都停在nullptr{if (pa == pb)return pa;//判断是否相同 相同代表有交点if (pa == nullptr)pa = headB;elsepa = pa->next;//每次pa只移动一次 if (pb == nullptr)pb = headA;else pb = pb->next;//每轮pb只移动一次}return nullptr;//没有交点
}
int main() {ListNode node1, node2, node3, node4, node5, node6, node7, node8;node1.val = 4;node1.next = &node2;node2.val = 1;node2.next = &node3;node3.val = 8;node3.next = &node4;node4.val = 4;node4.next = &node5;node5.val = 5;node5.next = nullptr;node6.val = 5;node6.next = &node7;node7.val = 6;node7.next = &node8;node8.val = 1;node8.next = &node3;ListNode* res = getIntersectionNode(&node1, &node6);if (res){cout << res->val << endl;}else {cout << "no intersection node" << endl;}return 0;
}

http://www.ppmy.cn/news/48419.html

相关文章

OpenAI-ChatGPT最新官方接口《速率并发限制》全网最详细中英文实用指南和教程,助你零基础快速轻松掌握全新技术(八)(附源码)

Rate limits 速率并发限制 前言Introduction 导言What are rate limits? 什么是速率限制&#xff1f;Why do we have rate limits? 为什么我们有速率限制&#xff1f;What are the rate limits for our API? 我们API的速率限制是什么&#xff1f;GPT-4 rate limits GPT-4速率…

记一次mysql cpu 异常升高100%问题排查

此服务器为一个从库&#xff0c;用于数据的导出业务&#xff0c;服务器配置较低&#xff0c;日常的慢sql也比较多。 上午11点左右cpu异常告警&#xff0c;如下图所示&#xff0c; cpu使用率突增到50%&#xff0c;下午2点左右突增到100% &#xff0c;登录服务器top命令查看cpu升…

计算机系统概述

计算机系统概述 计算机的发展史及未来展望计算机的基本概念及分类计算机的发展简史计算机未来展望 计算机组成结构计算机硬件组成计算机软件系统计算机系统的层次结构 计算机的发展史及未来展望 计算机的基本概念及分类 电子计算机是一种不需要人工直接干预&#xff0c;能够自…

Unity 位运算介绍及使用

介绍 位运算是指对二进制数的位&#xff08;bit&#xff09;进行操作的运算符&#xff0c;可以实现一些高效的逻辑和数学运算。Unity中常用的位运算符有以下几种&#xff1a; 与&#xff08;&&#xff09;&#xff1a;只有两个位都是1&#xff0c;结果才是1&#xff1b; …

基础排序算法【快速排序+优化版本+非递归版本】

基础排序算法【快速排序优化版本非递归版本】&#x1f4af;&#x1f4af;&#x1f4af; ⏰【快速排序】◽1.hoare法◽2.挖坑法◽3.前后指针法◽4.特性总结 ⏰【优化版本】◽1.随机选key◽2.三路取中◽3.小区间优化 ⏰【非递归版本】⏰【测试效率】排序OJ(可使用各种排序跑这个O…

camunda如何监控流程执行

在 Camunda 中&#xff0c;可以使用 Camunda 提供的用户界面和 API 来监控流程的执行情况。以下是几种常用的监控流程执行的方式&#xff1a; 1、使用 Camunda Cockpit&#xff1a;Camunda Cockpit 是 Camunda 官方提供的流程监控和管理工具&#xff0c;可以在浏览器中访问 Co…

Shiro安全框架简介

一、权限管理 1.1 什么是权限管理 基本上只要涉及到用户参数的系统都要进行权限管理&#xff0c;使用权限管理实现了对用户访问系统的控制&#xff0c;不同的用户访问不同的资源。按照安全规则或者安全策略控制用户访问资源&#xff0c;而且只能访问被授权的资源 权限管理包括认…

13.基于双层优化的电动汽车日前-实时两阶段市场竞标

MATLAB代码&#xff1a;基于双层优化的电动汽车日前-实时两阶段市场竞标 关键词&#xff1a;日前-实时市场竞标 电动汽车 双层优化 编程语言&#xff1a;MATLAB平台 内容简介&#xff1a;代码主要做的是电动汽车充电站市场竞标策略&#xff0c;采用双层优化模型对电动汽车…

内网穿透搭建

搭建内网穿透服务器搭建 1.frp frp官网 https://gofrp.org/ 简介 frp 是一个专注于内网穿透的高性能的反向代理应用&#xff0c;支持 TCP、UDP、HTTP、HTTPS 等多种协议。可以将内网服务以安全、便捷的方式通过具有公网 IP 节点的中转暴露到公网。 条件 公网服务器&…

Linux网桥简介、入门与配置

开始之前先得介绍一下什么是网桥&#xff0c;这里我们假设大家已经知道了物理的交换机是工作在链路层的。交换机的主要任务是在链路层查找转发表&#xff08;mac地址与端口对应关系表&#xff09;&#xff0c;按照数据帧的目标mac地址&#xff0c;转发数据帧到相应的端口。那么…

4.24、半关闭、端口复用

UNIX网络编程卷1&#xff1a;套接字联网API&#xff08;第3版&#xff09; 等文件(提取码&#xff1a;q99x) 4.24、半关闭、端口复用 1.半关闭2.端口复用 1.半关闭 当 TCP 链接中 A 向 B 发送 FIN 请求关闭&#xff0c;另一端 B 回应 ACK 之后&#xff08;A 端进入 FIN_WAIT_…

Java最新面试题100道,包含答案示例(1-10题)

1. Java 中什么是 JVM&#xff1f; JVM&#xff08;Java Virtual Machine&#xff09;即 Java 虚拟机&#xff0c;是一种能够在不同平台上运行 Java 程序的虚拟计算机。JVM 是 Java 的核心组成部分&#xff0c;它负责解释 Java 代码并将其转换成可执行的二进制字节码指令&…

13.弹出层.下

学习要点&#xff1a; 1. 基础参数 本节课我们来开始了解 Layui 的内置模块&#xff1a;弹出层的方法演示。 一&#xff0e;基础参数 1. 参数&#xff0c;我们主要通过 open 方法来演示&#xff0c;其它方法类似&#xff1b; layer . open ({ // 标题 title : 标…

004+limou+C语言链表之“有头双向有循环链表”的实现

0、前要 如果您是初步认识链表&#xff0c;或是不能完全“手撕”一个简单的单链表&#xff0c;可以看看我的上一篇有关“无头单向非循环链表”的实现&#xff0c;再来看这一篇文章 1、“有头双向有循环链表”的实现 &#xff08;0&#xff09;首先阐述两个节点的区别 头节点…

PostMan笔记(三)自动化测试

1. 简介 Postman是一款功能强大的API开发工具&#xff0c;也是一款流行的自动化测试工具。它提供了多种测试功能&#xff0c;包括测试脚本、预请求脚本和测试集合等。 1.1 测试脚本 测试脚本是Postman中用于自动化测试的核心部分。它可以使用JavaScript语言编写&#xff0c;…

WuThreat身份安全云-TVD每日漏洞情报-2023-04-19

漏洞名称:vm2 沙箱逃逸漏洞 漏洞级别:严重 漏洞编号:CVE-2023-29199,CNNVD-202304-1191 相关涉及:vm2 3.9.16 之前版本 漏洞状态:POC 参考链接:https://tvd.wuthreat.com/#/listDetail?TVD_IDTVD-2023-09144 漏洞名称:Linux 内核蓝牙子系统中存在 RCE 漏洞 漏洞级别:高危 漏洞…

LDMUI-001 61320946C模拟量模件的40端即直流24伏的负端接至逻辑地汇流排上

LDMUI-001 61320946C模拟量模件的40端即直流24伏的负端接至逻辑地汇流排上 ​ 八、现场接地常用注意事项 1.现场控制站 接地螺丝因机柜本体与底座间有胶皮形成绝缘&#xff0c;屏蔽地汇流排与底座间绝缘&#xff0c;现场控制站必须按规定做好接地处理。即分别接至现场控制站接…

#Chrome扩展程序开发教程--07:消息传递

#Chrome扩展程序开发教程--07&#xff1a;消息传递 引言1、基本介绍2、简单通信3、长时间通信4、其它通信4.1、Cross-extension messaging4.2、Sending messages from web pages4.3、Native messaging 引言 本系列博客旨在带来最新的Chrome扩展程序开发入门教程。 1、基本介绍 …

2023-03-18青少年软件编程(C语言)等级考试试卷(四级)解析

2023-03-18青少年软件编程(C语言)等级考试试卷(四级)解析T1、最佳路径 如下所示的由正整数数字构成的三角形: 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,和最大的路径称为最佳路径。你的…

DAY 40 firewalld 防火墙

firewalld防火墙是centos7系统默认的防火墙管理工具&#xff0c;取代了之前的iptables防火墙&#xff0c;也是工作在网络层&#xff0c;属于包过滤防火墙。 支持IPv4、IPv6防火墙设置以及以太网桥支持服务或应用程序直接添加防火墙规则接口拥有两种配置模式&#xff1a;临时模…