第 8 周 - 作业 1

用户头像
seng man
关注
发布于: 2020 年 07 月 26 日

以下两题,至少完成一道

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

请用(伪)代码描述算法,并给出时间复杂度和空间复杂度。





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



LinkedList<String> list1 = new LinkedList<>();
LinkedList<String> list2 = new LinkedList<>();
String element1 = "1";
String element2 = "2";
String element3 = "3";
String element4 = "4";
String element5 = "5";
list1.addAll(Arrays.asList(element1, element2, element3, element4, element5));
list2.addAll(Arrays.asList(element1, element3, element4, element5));
LinkedList<String> longList = list1.size() >= list2.size() ? list1 : list2;
LinkedList<String> shortList = list1.size() < list2.size() ? list1 : list2;
//看看两个节点是否相交
int diff = longList.size() - shortList.size();
for (int i = 0; i < longList.size(); i++) {
String node1 = list1.poll();
if (i < diff) {
continue;
}
String node2 = list2.poll();
if (node1 == node2) {
System.out.println(node2);
break;
}
}

空间复杂度:O(1)

时间复杂度:O(n)

发布于: 2020 年 07 月 26 日 阅读数: 16
用户头像

seng man

关注

还未添加个人签名 2018.12.04 加入

还未添加个人简介

评论 (1 条评论)

发布
用户头像
作业请加“极客大学架构师训练营”标签,便于分类
2020 年 07 月 27 日 17:00
回复
没有更多了
第8周-作业1