架构师训练营第八周作业

关注

发布于: 2020 年 12 月 11 日

问题一有两个单向链表（链表长度分别为m，n），这两个单向链表有可能在某个元素合并，也
可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，
如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元
素。
请用代码（或伪代码）描述算法，并给出时间复杂度。
﻿
﻿
解答：最直观的搞法是两次for循环，时间复杂度为O(mn):
for(Object a: listA){
    for(Object b: listB){
        if(a.equals(b)){
            return a;
        }
    }
}
根据题目分析，单向链表的特征是，单个元素后面只有一个指向，也就是说，如果两个链表是有相同的元素，那么从这个元素开始，后面所有的数据都是一样的。根据这个特点，我们可以通过只判断min(m,n)个元素就可以得出结论。这个算法的时间复杂度就是O(n)
int m = listA.size();
int n = listB.size();
int start = abs(m-n);
if(m > n){
    for(int i=0;i<listB;i++){
        if(listB.get(i).equals(listA.get(start+i))){
            return listB.get(i);
        }
    }
}else{
    for(int i=0;i<listA;i++){
        if(listA.get(i).equals(listB.get(start+i))){
            return listA.get(i);
        }
    }
}
﻿
问题二请画出DataNode服务器节点宕机的时候，HDFS的处理过程时序图
﻿
解答
﻿