架构师训练营第 1 期 - 第 8 周课后练习

关注

发布于: 2020 年 11 月 13 日

有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。请用代码（或伪代码）描述算法，并给出时间复杂度。
请画出 DataNode 服务器节点宕机的时候，HDFS 的处理过程时序图。

答：

代码实现如下：

单向链表类 SingleLinkedList，add 方法用来添加元素到链表中，getHead 方法用来返回头节点，size 方法用来返回链表的长度

package linkedlist;
public class SingleLinkedList {
    private HeadNode head;    private Node current;    private int size;
    public SingleLinkedList() {        head = new HeadNode();        size = 0;    }
    public void add(Object value) {        if (value == null) {            throw new IllegalArgumentException("Value cannot be null");        }        Node newNode = new Node();        newNode.value = value;        if (head.next == null) {            head.next = newNode;            current = head.next;        } else {            current.next = newNode;            current = current.next;        }        ++size;    }
    public HeadNode getHead() {        return head;    }
    public int size() {        return size;    }
    public static class HeadNode {        private Node next;
        public Node getNext() {            return next;        }    }
    public static class Node {
        private Object value;        private Node next;
        public Object getValue() {            return value;        }
        public Node getNext() {            return next;        }    }}

复制代码

工具类 LinkedListUtils 的 findMergeNode 用来查找 2 个单向链表是否存在合并元素，里面包含 2 层循环，第 1 层循环迭代单向链表 m 中的每一个元素，把每一个元素去跟单向链表 n 中的每一个元素比较，如果符合合并元素的要求，则记录合并节点，并在方法最后返回合并节点。整个方法的时间复杂度是 O(m*n)

package linkedlist;
public class LinkedListUtils {
    public static SingleLinkedList.Node findMergeNode(SingleLinkedList mList, SingleLinkedList nList) {        SingleLinkedList.HeadNode mHead = mList.getHead();        SingleLinkedList.HeadNode nHead = nList.getHead();
        if (mHead.getNext() == null || nHead.getNext() == null) {            return null;        }
        SingleLinkedList.Node mergeNode = null;        int m = mList.size();        int n = nList.size();        SingleLinkedList.Node mCurrent = mHead.getNext();
        for (int i = 0; i < m; ++i) {            SingleLinkedList.Node nCurrent = nHead.getNext();
            for (int j = 0; j < n; ++j) {                // 如果存在某个元素相等，剩下的元素也相等的话，那就是合并元素                if (isMergeable(mCurrent, nCurrent)) {                    mergeNode = mCurrent;                    break;                }                if (nCurrent.getNext() != null) {                    nCurrent = nCurrent.getNext();                }            }            if (mergeNode != null) {                break;            }            if (mCurrent.getNext() != null) {                mCurrent = mCurrent.getNext();            }        }
        return mergeNode;    }
    private static boolean isMergeable(SingleLinkedList.Node mCurrent, SingleLinkedList.Node nCurrent) {        boolean isMergeable = false;        if (mCurrent.getValue().equals(nCurrent.getValue())) {            isMergeable = true;
            SingleLinkedList.Node mNext = mCurrent.getNext();            SingleLinkedList.Node nNext = nCurrent.getNext();
            while (true) {                if (mNext != null && nNext == null) {                    isMergeable = false;                    break;                } else if (mNext == null && nNext != null) {                    isMergeable = false;                    break;                } else if (mNext != null && nNext != null) {                    if (!mNext.getValue().equals(nNext.getValue())) {                        isMergeable = false;                        break;                    }                    mNext = mNext.getNext();                    nNext = nNext.getNext();                } else {                    break;                }            }        }        return isMergeable;    }
    public static SingleLinkedList toList(Object... eles) {        SingleLinkedList mList = new SingleLinkedList();        for (Object ele : eles) {            mList.add(ele);        }        return mList;    }}

复制代码

单元测试类验证 findMergeNode 方法

package linkedlist;
import org.junit.Test;
public class TestLinkedListUtils {
    @Test    public void testFindMergeNode_2Lists_WithBeginMergeNode() {        SingleLinkedList mList = LinkedListUtils.toList("a", "b", "c", "d", "f", "g", "h", "i");        SingleLinkedList nList = LinkedListUtils.toList("a", "b", "c", "d", "f", "g", "h", "i");        SingleLinkedList.Node mergeNode = LinkedListUtils.findMergeNode(mList, nList);        assert mergeNode != null;        assert mergeNode.getValue().equals("a");    }
    @Test    public void testFindMergeNode_2Lists_WithMiddleMergeNode() {        SingleLinkedList mList = LinkedListUtils.toList("a", "b", "c", "d", "f2", "g", "h", "i");        SingleLinkedList nList = LinkedListUtils.toList("a", "b", "c", "d", "f", "g", "h", "i");        SingleLinkedList.Node mergeNode = LinkedListUtils.findMergeNode(mList, nList);        assert mergeNode != null;        assert mergeNode.getValue().equals("g");    }
    @Test    public void testFindMergeNode_2Lists_WithEndMergeNode() {        SingleLinkedList mList = LinkedListUtils.toList("a", "b", "c", "d", "d", "g", "h2", "z");        SingleLinkedList nList = LinkedListUtils.toList("a", "b", "c", "d", "f", "g", "h", "z");        SingleLinkedList.Node mergeNode = LinkedListUtils.findMergeNode(mList, nList);        assert mergeNode != null;        assert mergeNode.getValue().equals("z");    }
    @Test    public void testFindMergeNode_2Lists_WithoutMergeNode() {        SingleLinkedList mList = LinkedListUtils.toList("a", "b", "c", "d", "f", "g", "h", "h");        SingleLinkedList nList = LinkedListUtils.toList("a", "b", "c", "d", "f", "g", "h", "i");        SingleLinkedList.Node mergeNode = LinkedListUtils.findMergeNode(mList, nList);        assert mergeNode == null;    }}

复制代码

假设 HDFS 中有 4 个 DataNode 节点，DataNode 1 节点宕机了，那么处理过程的时序图如下：

1. DataNode 1 宕机了，无法发送心跳给 NameNode
2. NameNode 长时间内没有接收到 DataNode 1 的心跳，则认为节点已经宕机
3. NameNode 在元数据中查找 DataNode 1 所有数据块的信息，比如有数据块 A、数据块 B、数据块 C
4. NameNode 根据数据块查找到这些数据块所在的 DataNode 信息，比如数据块 A 的副本分别在 DataNode 1、DataNode 2、DataNode 3，数据块 B 的副本分别在 DataNode 1、DataNode 3、DataNode 4，数据块 C 的副本分别在 DataNode 1、DataNode 2、DataNode 4
5. 发送指令复制 DataNode 2 上的数据块 A，复制新的副本到 DataNode 4
6. 发送指令复制 DataNode 3 上的数据块 B，复制新的副本到 DataNode 2
7. 发送指令复制 DataNode 4 上的数据块 C，复制新的副本到 DataNode 3

发布于: 2020 年 11 月 13 日阅读数: 38

Anyou Liu

关注

还未添加个人签名 2019.05.24 加入

还未添加个人简介

发布

暂无评论

创作场景

架构师训练营第 1 期 - 第 8 周课后练习

Anyou Liu

评论