架构师训练营第八周 - 作业
作业:有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,如下图所示的这样,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。
请用(伪)代码描述算法,并给出时间复杂度。
伪代码算法描述:
1.将链表1和链表2的元素分别存储到一个HashMap中
2.遍历链表1的元素与链表2的元素一一比对,有相同的就return出该元素并跳出循环,即有返回值的为合并且返回值就是X元素,无则未合并
时间复杂度=O(m,n)
版权声明: 本文为 InfoQ 作者【人世间】的原创文章。
原文链接:【http://xie.infoq.cn/article/c44154e0076fd22efbe0bfddf】。
本文遵守【CC-BY 4.0】协议,转载请保留原文出处及本版权声明。
评论