【架构师训练营第 1 期 08 周】作业

关注
发布于: 2020 年 11 月 15 日
【架构师训练营第 1 期 08 周】 作业
﻿
1.有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用代码（或伪代码）描述算法，并给出时间复杂度。
﻿
2.请画出 DataNode 服务器节点宕机的时候，HDFS 的处理过程时序图。
﻿
解答：
1.
先分析题目关键词：
单向链表：不是双向的，分为有环和无环，有环即最后一个元素的指针指向链表中其中一个元素（可以生动理解为数字“6”的书写顺序），无环即最后一个元素的指针指向null；
合并：单向链表如果有元素合并，即这个元素后面的所有元素完全相同，因为每个元素的指针都指向相同的下一个元素。
思路：
如果有环的情况下，两个链表的环肯定是大小一样的，所以最好先把链表解环，把最后一个元素的next指针变成null，这样所有方式都是通过对比无环链表来寻找合并元素。解环通过双指针来解，只要能套圈就是有环。
无环情况下：
第一种方法最简单粗暴，双循环嵌套查询，匹配相同则会合并，如果指针不相同就不会合并，时间复杂度O(n^2)；
第二种方法利用链表合并的特性，得出两个链表如果合并，则从后往前的p个元素完全一致，且p小于等于m和n之间的最小值。
这样取出链表放入队列中，修整长度后，一起比较，存在相等的元素则会合并，而且第一个相等的元素就是第一个合并的元素。时间复杂度：O(2m+n)
节点数据结构：
public class LinkNode {
    private Object value;
    private LinkNode next;
﻿
    LinkNode(Object value) {
        this.value = value;
    }
﻿
    public Object getValue() {
        return value;
    }
﻿
    public void setValue(Object value) {
        this.value = value;
    }
﻿
    public LinkNode getNext() {
        return next;
    }
﻿
    public void setNext(LinkNode next) {
        this.next = next;
    }
}
﻿
代码实现：
public class Test08 {
    public static void main(String[] args) {
        // 初始化
        LinkNode a = new LinkNode("a");
        LinkNode b = new LinkNode("b");
        LinkNode d = new LinkNode("d");
        LinkNode e = new LinkNode("e");
        LinkNode f = new LinkNode("f");
        LinkNode x = new LinkNode("x");
        LinkNode y = new LinkNode("y");
        LinkNode z = new LinkNode("z");
        a.setNext(b);
        b.setNext(x);
        x.setNext(y);
        y.setNext(z);
        d.setNext(e);
        e.setNext(f);
        f.setNext(x);
        // 使用两个头指针判断是否合并
        getFirstMergeNode(a, d);
    }
﻿
    private static LinkNode getFirstMergeNode(LinkNode pointHead1, LinkNode pointHead2) {
        // 获取两个链表的最短长度，时间复杂度O(m+n)
        int size1 = 0;
        LinkNode node1 = pointHead1;
        while (node1 != null) {
            size1++;
            node1 = node1.getNext();
        }
        int size2 = 0;
        LinkNode node2 = pointHead2;
        while (node2 != null) {
            size2++;
            node2 = node2.getNext();
        }
        // 两个链表的最短长度
        int minSize = size1 > size2 ? size2 : size1;
        // 当前node跳到较长的链表size-minSize位置，使两个链表变成相同的长度，再开始比较。时间复杂度O(maxSize-minSize)
        node1 = pointHead1;
        node2 = pointHead2;
        if (size1 > size2) {
            while (size1 - minSize > 0) {
                node1 = pointHead1.getNext();
                size1--;
            }
        } else if (size1 < size2) {
            while (size2 - minSize > 0) {
                node2 = pointHead2.getNext();
                size2--;
            }
        }
        // 开始对比，时间复杂度O(minSize)
        while(node1.getNext() != null && node2.getNext() != null) {
            if(node1.getNext() == node2.getNext()) {
                System.out.println("link1和link2可以合并,合并点为："+node1.getNext().getValue()+"。");
                return pointHead1;
            } else {
                node1 = node1.getNext();
                node2 = node2.getNext();
            }
        }
        System.out.println("link1和link2不可以合并。");
        return null;
    }
}
﻿
﻿
第三种网上看到介绍Stack Overflow一个优雅的写法，利用两个链表长度差，循环位移对比，如果有相同的元素则返回。两个元素相同的时候如果是null即不合并，如果不是null即会合并。其实也和方法二前半段思路一样，最终实现链表对齐比较。
链接：https://stackoverflow.com/questions/1594061/check-if-two-linked-lists-merge-if-so-where/14956113#14956113
﻿
2.HDFS处理DataNode宕机时序图
﻿