Week 08 命题作业

以下两题，至少完成一道

作业一

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

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





如果两个链表相交，那么相交点之后的长度是相同的

我们需要做的事情是，让两个链表从同距离末尾同等距离的位置开始遍历。这个位置只能是较短链表的头结点位置。

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

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

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

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

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

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



作业二

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