第八周 性能优化(二) 作业 「架构师训练营 3 期」
有两个单向链表(链表长度分别为 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)
评论