首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
开心就好e
Java
发布于上海
关注
已关注
取消关注
@Maokt:
题解 | #两个链表的第一个公共结点#
算法思想一:双指针 解题思路: 使用两个指针 a,b 分别指向两个链表 pHead1,pHead2的头结点,然后同时分别逐结点遍历,当 a 到达链表 pHead1的末尾时,重新定位到链表 pHead2的头结点;当 b 到达链表 pHead2 的末尾时,重新定位到链表 pHead1的头结点。当双指针相遇时,所指向的结点就是第一个公共结点 图解: 代码展示: Python版本 class Solution: def FindFirstCommonNode(self , pHead1 , pHead2 ): # write code here a = pHead1 b = pHead2 # 当两者相同则是第一个公共节点 while a!=b: # a从pHead1遍历完再遍历pHead2 a = a.next if a else pHead2 # b从pHead2遍历完再遍历pHead1 b = b.next if b else pHead1 return a 复杂度分析 时间复杂度O(M+N):M, N分别表示 pHead1, pHead2的链表长度,最差情况下需要遍历完两个链表 空间复杂度O(1):仅使用常数级变量空间 算法思想二:集合set 解题思路: 做这题最容易想到的一种解决方式就是先把第一个链表的节点全部存放到集合set中,然后遍历第二个链表的每一个节点,判断在集合set中是否存在,如果存在就直接返回这个存在的结点。如果遍历完了,在集合set中还没找到,说明他们没有相交,直接返回null即可 代码展示: JAVA版本 import java.util.*;/*public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }}*/public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { //创建集合set Setset = new HashSet<>(); //先把链表1的结点全部存放到集合set中 while (pHead1 != null) { set.add(pHead1); pHead1 = pHead1.next; } //然后访问链表2的结点,判断集合中是否包含链表2的结点,如果包含就直接返回 while (pHead2 != null) { if (set.contains(pHead2)) return pHead2; pHead2 = pHead2.next; } //如果集合set不包含链表2的任何一个结点,说明没有交点,直接返回null return null; }} 复杂度分析 时间复杂度O(M+N):M, N分别表示 pHead1, pHead2的链表长度,最差情况下需要遍历完两个链表 空间复杂度O(M):需要额外集合空间存储 pHead1 结点 算法思想三:统计两个链表的长度 解题思路: 还可以先统计两个链表的长度,如果两个链表的长度不一样,就让链表长的先走,直到两个链表长度一样,这个时候两个链表再同时每次往后移一步,看节点是否一样,如果有相等的,说明这个相等的节点就是两链表的交点,否则如果走完了还没有找到相等的节点,说明他们没有交点,直接返回null即可 图解: 代码展示: JAVA版本 public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { //统计链表A和链表B的长度 int lenA = length(pHead1), lenB = length(pHead2); //如果节点长度不一样,节点多的先走,直到他们的长度一样为止 while (lenA != lenB) { if (lenA > lenB) { //如果链表A长,那么链表A先走 pHead1 = pHead1.next; lenA--; } else { //如果链表B长,那么链表B先走 pHead2 = pHead2.next; lenB--; } } //然后开始比较,如果他俩不相等就一直往下走 while (pHead1 != pHead2) { pHead1 = pHead1.next; pHead2 = pHead2.next; } //走到最后,最终会有两种可能,一种是headA为空, //也就是说他们俩不相交。还有一种可能就是headA //不为空,也就是说headA就是他们的交点 return pHead1; } //统计链表的长度 private int length(ListNode node) { int length = 0; while (node != null) { node = node.next; length++; } return length; }} 复杂度分析 时间复杂度O(M+N):M, N分别表示 pHead1, pHead2的链表长度,最差情况下需要遍历完两个链表 空间复杂度O(1):仅使用常数级空间变量
点赞 30
评论 5
全部评论
推荐
最新
楼层
滴滴
校招火热招聘中
官网直投
相关推荐
code5bug
05-11 12:13
Java
篮球游戏 - 华为OD统一考试(D卷)
OD统一考试(D卷) 分值: 100分 题解: Java / Python / C++ 题目描述 幼儿园里有一个放倒的圆桶,它是一个线性结构,允许在桶的右边将篮球放入,可以在桶的左边和右边将篮球取出。 每个篮球有单独的编号,老师可以连续放入 一个或多个篮球,小朋友可以在桶左边或右边将篮球取出,当桶里只有一个篮球的情况下,必须从左边取出。 如老师按顺序放入1、2、3、4、5 共5个编号的篮球,那么小朋友可以依次取出的编号为“1,2,3,4,5”或者“3,1,2,4,5”编号的篮球,无法取出 “5,1,3,2,4” 编号的篮球。 其中“3,1,2,4,5”的取出场景为: 连续放入1,2,3...
投递华为等公司10个岗位 >
2024华为OD机试真题...
点赞
评论
收藏
转发
17Cl
05-13 23:21
中国科学院大学 计算机类
校招决赛圈
多模态相关方向,个人还是喜欢稍微卷一卷,主要看重发展前景,三个都是ssp,纠结。
点赞
评论
收藏
转发
吃饭加个蛋
03-26 18:38
门头沟学院 计算机类
哈哈
点赞
评论
收藏
转发
适彼乐土
05-12 22:01
重庆大学 计算机类
19年的鱼皮差点进不去腾讯
挖坟翻到鱼皮19年发的帖子,在犹豫保研还是留腾讯。如果选后者是不是这辈子都进不去腾讯后台开发了?😋22年腾讯校招应该是200hc?
点赞
评论
收藏
转发
Java三段
05-14 17:21
Java
经验分享:春招零Offer,5月份还有机会吗?
先说答案:5 月份依然有拿到 Offer 的机会。 5月份春招结束了吗? 对于应届大学生来说(也就是今年暑假毕业的学生),5 月中旬春招就陆续结束了,但是 5 月份会有很多补录的机会。 对于非应届的大学生来说(今年之后毕业的学生)来说,5 月和 6 月正是在暑假最好的时机,尤其是 6 月份会有大量的暑假实习岗的招聘需求。 对于社招的同学来说,5 月份之后岗位招聘的需求,相比于前两个月会有一个明显的减少,但依然会有招聘的需求,这就好比去景区旅游的人一样,节假日一定是最多的,但非节假日也会有一些人去逛。 为什么会有补录? 因为有一些人可能拿到了很多家公司的 Offer,但最终只能选择一家公司。...
大家都开始春招面试了吗
点赞
评论
收藏
转发
点赞
收藏
评论
分享
回复帖子
全站热榜
1
...
携程oc了
2.6W
2
...
美团-Java后端-平台技术部-一面凉经(复活赛)
1.3W
3
...
比亚迪机械面经&薪资爆料&面试题目&解答思路
1.3W
4
...
【话术建议】求职者和企业的互骗话术?
8850
5
...
瑞幸java校招二面(史诗级80min)
7731
6
...
滴滴秋储后端(秒挂)
5215
7
...
快手二面g
5042
8
...
【进面核心】如何紧盯个人简历与企业需求的契合度
4895
9
...
字节抖音电商后端日常实习一二三面已oc
4664
10
...
腾讯 后台开发 一面
4235
正在热议
#
牛客帮帮团来啦!有问必答
#
710386次浏览
11527人参与
#
许愿池
#
77202次浏览
1542人参与
#
通信硬件人笔面经互助
#
107752次浏览
2178人参与
#
你的秋招进展怎么样了
#
500896次浏览
13425人参与
#
找工作时遇到的神仙HR
#
177662次浏览
1744人参与
#
如何写一份好简历
#
259316次浏览
3918人参与
#
铜五铁六真的存在吗?
#
27340次浏览
293人参与
#
找工作,你会甘心进小厂还是猛冲大厂
#
35048次浏览
352人参与
#
产品实习,你更倾向大公司or小公司
#
35949次浏览
548人参与
#
非技术岗是怎么找实习的
#
73864次浏览
1385人参与
#
市场营销面经
#
4549次浏览
125人参与
#
互联网公司评价
#
79565次浏览
1087人参与
#
通信硬件薪资爆料
#
196315次浏览
1759人参与
#
你的秋招进行到哪一步了
#
353009次浏览
6269人参与
#
硬件兄弟们 甩出你的华为奖状
#
27515次浏览
180人参与
#
无实习如何秋招上岸
#
224693次浏览
3518人参与
#
投了多少份简历才上岸
#
56666次浏览
947人参与
#
面试中的破防瞬间
#
82577次浏览
1015人参与
#
通信/硬件的薪资开多少,才值得去?
#
10743次浏览
140人参与
#
产品人求职现状
#
50591次浏览
747人参与
牛客网
牛客企业服务