Leetcode_相交链表

devtools/2024/9/23 9:35:38/

✨✨所属专栏:LeetCode刷题专栏✨✨

✨✨作者主页:嶔某✨✨

题目:

 题解:

看到这个题目首先我们要排除链表逆置的想法,如图、因为c1节点只有一个next指针,逆置后不可能同时指向a2和b3节点。

其次有的的同学想到一个一个节点来比较值,首先这是错误的。

第一:AB两个链表的长度不一定相同,不能相比。

第二:比较节点中的值有一定的特殊情况,我们要比的时节点的地址。

常规解法:

先分别算出A、B两个链表的长度lenA,lenB,先让长的链表的头指针走|lenA - lenB|,然后再一起走,以longlist != shortlist为循环的终止条件

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{   int lenA = 0;int lenB = 0;struct ListNode *cur1 = headA;struct ListNode *cur2 = headB;while(cur1->next){lenA++;cur1 = cur1->next;}while(cur2->next){lenB++;cur2 = cur2->next;}int Difference = abs(lenA - lenB);   struct ListNode *longlist = headA;struct ListNode *shortlist = headB;if(lenA < lenB){longlist = headB;shortlist = headA;}while(Difference--)longlist = longlist->next;while(longlist && shortlist){if(longlist == shortlist)return longlist;longlist = longlist->next;shortlist = shortlist->next;}return NULL; 
}

大神解法:

让A链表从头遍历,当pA为空时,pA = headB;B链表从头遍历,当pB为空时,pB = headA。让每个链表都走完两个链表的路程,最后它们一定会在相交节点处相遇

 

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

本期博客到这里就结束了,如果有什么错误,欢迎指出,如果对你有帮助,请点个赞,谢谢!


http://www.ppmy.cn/devtools/25332.html

相关文章

(iFlyCode、FREEGPT、Copilot、AIPlus、稳定高效)分享好用的ChatGPT

目录 1、iFlyCode 2、FREEGPT 3、Microsoft Copilot: 你的日常 AI 助手 4、AIPlus

web server apache tomcat11-24-Virtual Hosting and Tomcat

前言 整理这个官方翻译的系列&#xff0c;原因是网上大部分的 tomcat 版本比较旧&#xff0c;此版本为 v11 最新的版本。 开源项目 从零手写实现 tomcat minicat 别称【嗅虎】心有猛虎&#xff0c;轻嗅蔷薇。 系列文章 web server apache tomcat11-01-官方文档入门介绍 web…

GaussDB轻量化运维管理工具介绍

前言 本期课程将从管理平台的架构出发&#xff0c;结合平台的实例管理、实例升级、容灾管理和监控告警的功能和操作介绍&#xff0c;全面覆盖日常运维操作&#xff0c;带您理解并熟练运用GaussDB运维平台完成运维工作。 一、GaussDB 运维管理平台简介 开放生态层 友好Web界面…

怎么用电子章盖骑缝章?

使用电子章盖骑缝章通常涉及以下步骤&#xff0c;具体操作可能会因使用的电子签章软件或平台有所不同&#xff0c;但基本流程相似&#xff1a; 准备电子文档&#xff1a; 打开或上传需要加盖骑缝章的电子文档&#xff0c;通常支持PDF、Word等常见格式。 选择骑缝章功能&#xf…

webpack3升级webpack4遇到的各种问题汇总

webpack3升级webpack4遇到的各种问题汇总 问题1 var outputNamecompilation.mainTemplate.applyPluginWaterfull(asset-path,outputOptions.filename,{......)TypeError: compilation.mainTemplate.applyPluginsWaterfall is not a function解决方法 html-webpack-plugin 版…

使用 Docker 自建一款怀旧游戏之 - 扫雷

1&#xff09;扫雷 简介 扫雷 是一种经典的单人电脑游戏&#xff0c;最初由微软公司在 1990 年代开发并内置在 Windows 操作系统中。游戏的目标是在一个由方块组成的网格上揭开所有非地雷的方块&#xff0c;而不触发地雷。每个方块上都标有数字&#xff0c;表示周围 8 个方块中…

通过AI助手实现一个nas定时任务更新阿里云域名解析

一.通过AI助手实现一个ip-domain.py的脚本 起一个Python脚本&#xff0c;ip-domain.py&#xff1b;注意已安装Python3.的运行环境&#xff1b;将下面阿里云相关配置添加&#xff0c;注意这里引用了两个包&#xff0c;requests和alibabacloud_alidns20150109&#xff1b;执行前…

Linux安装Maven

目录 传送门前言一、下载二、安装三、配置 传送门 SpringMVC的源码解析&#xff08;精品&#xff09; Spring6的源码解析&#xff08;精品&#xff09; SpringBoot3框架&#xff08;精品&#xff09; MyBatis框架&#xff08;精品&#xff09; MyBatis-Plus SpringDataJPA Spr…