写点什么

第八周 性能优化(二) 作业 「架构师训练营 3 期」

用户头像
feiyun123
关注
发布于: 2021 年 01 月 17 日

有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,也可能不合并,如下图所示的这样。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。

请用代码(或伪代码)描述算法,并给出时间复杂度。


思路:

两个单向链表在某个元素合并的情况下,也就是从某个元素开始链表合并元素向下的一段内容是相同的,长度相同,内容相同。

也有可能不合并,也就是尾部没有相同的一个或一段。


实现的代码逻辑:

for(链表 1){//遍历链表 1

a//链表 1 元素

list1//a 元素及向下的链表内容

for(链表 2){//遍历链表 2

b//链表 2 元素

if(a==b){//当两链表中元素相同时

len1//a 向下的长度

len2//b 向下的长度

if(len1!=len2||len2<len1){continue;}//长度不一致或当 len2 小于 len1 继续向下判断,

list2//b 元素及向下的链表内容

if(len1==len2){

if(list1 与 list2 内容顺序相同) //找到合并的元素是当前的 a

if(list1 与 list2 内容顺序不相同){continue;}

}


}


}

时间复杂度:O(m*n)


用户头像

feiyun123

关注

还未添加个人签名 2019.09.28 加入

还未添加个人简介

评论

发布
暂无评论
第八周 性能优化(二) 作业 「架构师训练营 3 期」