架构师训练营第 1 期 - 第八周作业

作业一：

（至少完成一个）

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

请用代码（或伪代码）描述算法，并给出时间复杂度。

先想一个脑海中首次想到的最简单的办法(有时候最简单的方法最有效也不容易出错,但是有时候显得很愚蠢,要看具体情况而定):

1. 遍历链表 1,将链表 1 的所有元素放到 Set 中

2. 遍历链表 2,判断是否存在于这个 Set,如果存在则取出后继续遍历,取出的所有元素即为合并元素.

这个办法的时间复杂度为 O(m+n) 应该可以理解为 O(2n)

但是这个办法有一个硬伤,如果链表 1 或者链表 2 中本身就有重复元素,那么这个方法是得不到正切值的.

而且忽略了判断 Set 中是否存在元素的时间复杂度

为了避免这个情况,再想一个简单的办法:

如果链表合并,意味着指针地址相等,在 Java 中,不要使用类似 equals()方法去判断变量指向的元素,而直接使用 == 判断指向元素的变量是否相等,即可知道两个变量是否指向了同一个元素.

1. 双层循环,外层循环遍历链表 1

2. 内层循环遍历链表 2

3. 在内层循环中,直接判断 循环 1 的迭代变量 == 循环 2 的迭代变量

4. 如果相等则为合并元素,循环继续取出则为合并列表

这个办法的时间复杂度为 O(m*n) 应该可以算作 O(n^2)

然后 1 和 2 应该可以结合一下,降低办法 2 的时间复杂度