第八周大作业

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



算法思路：

假设链表A和链表B的公共长度为k(k>=0)，A的长度为n+k, B的长度为m+k。

启用两个指针p，q，分别指向链表A，B的头节点，开始遍历，当指针p走到A的尾节点时，将p重新指向B的头节点，同样当指针q走到B的尾节点时，将q重新指向A的头节点。最终p，q指针一定会在第一个公共节点相遇，因为此时p指针的路径长度为n+k+m，q指针的路径长度为m+k+n，当没有公共节点的时候，p，q 指针会同时指向null。

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode nodeA = headA;
        ListNode nodeB = headB;
        while(nodeA != nodeB) {
            nodeA = nodeA != null ? nodeA.next : headB;
            nodeB = nodeB != null ? nodeB.next : headA;
        }
        return nodeA;
    }



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

1，NameNode检测到故障节点在数个时间周期未发送心跳报告

2，NameNode检查故障节点管理的数据块，向其他所有正常节点发出复制请求。

3，拥有对应的数据块的节点将数据块复制到故障节点所在机架。

4，复制完成后数据节点向NameNode发送心跳报告，报告其所管理的数据块信息。