伪代码如下：
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链表无交点 }}
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 进行遍历）
还未添加个人签名 2019.11.08 加入
还未添加个人简介
京公网安备 11010502039052号京公网安备 11010502039052号京公网安备 11010502039052号
评论