Week 08 命题作业

用户头像
Jeremy
关注
发布于: 2020 年 07 月 29 日
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 的处理过程时序图。







用户头像

Jeremy

关注

还未添加个人签名 2018.01.21 加入

还未添加个人简介

评论 (1 条评论)

发布
用户头像
作业请添加“极客大学架构师训练营”标签,便于分类
2020 年 07 月 29 日 17:49
回复
没有更多了
Week 08 命题作业