第八作业

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

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

分析

两个链表，如果发生合并，后面的元素则一定相同。从头开始，找出两个链表第一次匹配的位置，依次往后比较，如果全部相同，则认为可以合并。

思路一，穷举法

问题是要寻找两个链表的合并节点，那么第一个直观的想法就是穷举法。顺序对第一个链表中的每一个节点，查看其在第二个链表中是否存在；若存在，则说明该节点就是两个链表的第一个合并点；若找不到，则说明两个链表没有合并。这个算法的时间复杂度为 O(m*n)。伪代码如下。

思路二，以空间换时间

在第一个思路中，我们很容易发现，第二个链表被检查过很多遍，最坏情况（找不到合并点）下对每个节点都查找了一遍。那能不能在查找一遍就把结果记在某个地方，以后直接查找而不用在遍历一遍呢？

在很多编程语言中都有 Dictionary 这种数据结构，它的一个特点就是查询的时间复杂度是 O(1)，即用 key 可以直接查得结果。Dictionary 是用哈希算法实现这个 O(1)复杂度的查询。假设哈希算法时间开销相比这个链表查询开销小很多的话，可以用 Dictionary 和下面的算法来解决问题，时间复杂度和空间复杂度都是 O(m+n)。伪代码如下。

2. 请画出 DataNode 服务器节点宕机的时候，HDFS 的处理过程时序图。