架构师训练营第八周命题作业
有两个单向链表(链表长度分别为m,n),这两个单向链表有可能在某个元素合并,如下图所示的这样,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。
请用(伪)代码描述算法,并给出时间复杂度和空间复杂度。
请画出DataNode服务器节点宕机的时候,HDFS的处理过程时序图。
1 判断链表合并算法
设给出的两个链表为 A 和 B,长度分别为 m 和 n。
将链表 A 的尾节点与链表 B 的头节点相连,将链表 B 的尾节点与链表 A 的头节点相连。
从链表 A 和链表 B 的头结点开始遍历,设当前遍历到的结点分别为 p 和 q。
如果 p 和 q 为同一节点,则两链表合并且该结点为合并的元素。
如果遍历 m+n 次后未找到,则两链表不合并。
在具体实现中,不需要真正将两个链表头和尾连接起来,只需要判断当迭代变量为空时将另一个链表的头赋过去就可以了。如果两个链表合并则该函数返回合并处结点的指针。当进行了 m+n 次迭代后,此时 p 与 q 都为空指针,循环退出,返回空指针。因此,当两个链表不合并时,该函数返回空指针。
该算法的时间复杂度为O(m+n),因为每个链表最多会被遍历两次。
该算法的空间复杂度为O(1),因为只申请了两个迭代变量。
2 HDFS 失效时序图
当 HDFS 中有数据节点失效时,以数据节点 F 失效为例,名称节点会由于没有收到数据节点 F 发送的心跳检查而检测到数据节点 F 失效。接着名称节点会检查数据节点 F 中包含的数据块,以数据块 i 为例,查看其他包含数据块 i 的数据节点。若数据节点 X 包含数据块 i ,再寻找另一个不包含该数据库的数据节点 Y,将数据块 i 复制到数据节点 Y 上。
版权声明: 本文为 InfoQ 作者【whiter】的原创文章。
原文链接:【http://xie.infoq.cn/article/77078ad6efa5d7ba95d84eb78】。未经作者许可,禁止转载。
评论