【第八周】命题作业——链表合并判断及其复杂度和 HDFS 节点容错

以下两题，至少完成一道

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

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





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



答：

1、链表问题

思路：

基于链表特点，如果两个链表的节点重合了，那么重合节点之后的所有节点都是相同节点。也就是说，重合节点处在两个链表的同一个倒序数值位置。所以，假设知道两个链表长度，那么只要较长链表指针后移m-n个节点后，获取双方节点进行逐个比较，即可判断两个链表是否有重合。



时间复杂度O(n)，空间复杂度O(0)。



过程（代码略）：

1、已知链表M和N，长度分别为m和n，且m>n

2、将链表M的指针后移m-n个节点

3、分别读取链表M、N的当前指针所指节点，进行比较

4、若两个节点不同，且没有后续节点，则链表未合并，退出

5、若两个节点不同，但还有后续节点，链表M和N的指针都后移，继续执行步骤3

6、若两个节点相同，则链表合并，结束退出

2、HDFS节点容错时序图

HDFS架构图



HDFS数据节点容错时序图：