第八周作业
以下两题,至少完成一道
一、有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,如下图所示的这样,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。
请用(伪)代码描述算法,并给出时间复杂度和空间复杂度。
二、请画出 DataNode 服务器节点宕机的时候,HDFS 的处理过程时序图
第一题:
LinkedList linkm,linkn;
Long[] linkArray = new Long[m];
nodeM = linkm.first;
for (int i=0;i<m;i++){
linkArray[i]=nodeM.hashCode;
nodeM = nodeM.next;
}
int i=0;
Long hc;
nodeN = linkn.first;
// 是否合并
isUnion = False;
while (i<n){
hc = nodeN.hashCode;
for (int j=0;j<m;j++){
if (hc == linkArray[j]){
isUnion = True;
break;
}
}
if (isUnion)
break;
i++;
nodeN=nodeN.next;
}
时间复杂度O(n^2)
空间复杂度O(n)
版权声明: 本文为 InfoQ 作者【王鑫龙】的原创文章。
原文链接:【http://xie.infoq.cn/article/1a5625d525e334ae65cc68ca0】。
本文遵守【CC BY-NC】协议,转载请保留原文出处及本版权声明。
评论