架构师训练营 第八周【作业】

用户头像
小K
关注
发布于: 2020 年 07 月 29 日

题一、有两个单向链表(链表长度分别为 m,n),在不修改链表的情况下,快速地判断这两个链表是否合并,并找到合并的元素,也就是图中的 x 元素。请用(伪)代码描述算法,并给出时间复杂度。



伪代码如下:

public static void main(String[] args) {
node a;//链表a,长度为m
node b;//链表b,长度为n
//首先,将a、b中,长度较长的一个链表,存入hashmap中,以便快速查找。假设m>n,a链表较长
putInHashmap(hashmap,a);//将链表a的所有元素存入hashmap中
x=null;//x为合并元素
while(b.next!=null){//遍历链表b
if(b.next在hashmap中存在){
x=b.next;//找到合并的x元素
break;
}
}
if(x!=null){
//找到x元素
}else{
//未找到x元素,a、b链表无交点
}
}

代码存在一个循环,并且hashmap的查找时间复杂度是O(1),所以以上代码的综合时间复杂度只和链表b的数量级有关,为O(n)

(注:假设m>n,所以取长度为n的链表b进行遍历)

用户头像

小K

关注

还未添加个人签名 2019.11.08 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营 第八周【作业】