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

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





1. 暴力法：遍历两条链表，判断是否有相同的节点，若有，判断两条链表合并。时间复杂度为O(n^2)。

2. hash法：hash来判断，将两个链表的节点进行hash，然后判断出节点。时间复杂度为O(n)。

3. 末尾节点判断法：遍历到两条链表末尾节点是否一致，若一致则两个链表有合并。将长度较长的链表指针向后移动两个链表长度的差值，然后在开始遍历两个链表，判断节点是否相同即可。时间复杂度为O(n)。

可参考LeetCode 160.相交链表

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

• 高可用过程（DataNode失效）

1. DateNode启动后会向NameNode注册。

2. DateNode定时向NameNode发送心跳。

3. 当DataNode超时没有向NameNode发送心跳，NameNode判定DataNode失效。

4. NameNode通过元（meta）信息检查该失效DataNode的数据块有哪些，备份数据块在哪里。

5. NameNode通知备份机复制失效DataNode的数据块（在多台服务器均匀分布）到某备份节点，恢复成三副本。

HDFS高可用过程（DataNode失效）时序图