Author： Jessie

Date:  2020/7/28   V1.0



两条单向链表是否合并的查找算法



有两个单向链表（链表长度分别为m，n）。这两个单向链表有可能在某个元素合并，如下图所示的这样，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速判断这两个链表是否合并？如果合并，找到合并的原则，也就是图中的x元素。

请用（伪）代码描述算法，并给出时间复杂度。



方法一：

采用暴力的方法，遍历两个链表，判断第一个链表的每个结点是否在第二个链表中，时间复杂度为O(m*n)，耗时很大。

方法二：

如果两个链表合并，那么最后的节点的地址一定相同。时间复杂度为O（m+n）。

伪代码实现：

node findNode（node A, node B）

{ 

   node p1,p2;

   p1=A;

   p2=B;

 

   if(p1==null || p2==null) {

       return null；

   }
 

   //查找链表2结束节点

   int m=0;

   while（p1.next!=null）{

        p1 = p1.next;

        m++;

    }

 

//查找链表2结束节点

  int n=0;

   while（p2.next!=null）{

        p2 = p2.next;

        n++;

    }

 

 if(p1！=p2)

    return null；

 

  //判断交叉点

  int diff = abs( m-n);

  if(m>n){

    p1=A;

     p2=B;

  } else{

    p1=B;

    p2= A;

  }

  

  for(int i=0;i<diff;i++){

     p1=p1.next；

  }

  while（ p1!=p2）{

   p1= p1.next;

   p2=p2.next;

  }

  return p1;

}




DataNode服务节点宕机，HDFS处理时序图



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



HDFS写文件具体流程如下：

1.客户端端首先通过DistributedFileSystem对象的create方法创建一个FSDataOutputStream（输出流）对象；

2.客户端通过DistributedFileSystem对象向NameNode发起一次RPC调用，在HDFS的Namespace中创建一个文件条目；

3.通过FSDataOutputStream对象，向DataNode写入数据，数据首先被写入FSDataOutputStream对象内部的Buffer中，然后数据被分割成一个个Packet数据包；

4.以Packet最小单位，基于Socket连接发送到按特定算法选择的HDFS集群中一组DataNode中的一个节点上，在这组DataNode组成的Pipeline（数据量管道）上依次传输Packet；

5.这组DataNode组成的Pipeline反方向上，发送ack，最终由Pipeline中第一个DataNode节点将Pipeline ack发送给客户端；

6.完成向文件写入数据，客户端在FSDataOutputStream对象上调用close方法，关闭流；

7.调用DistributedFileSystem对象的complete方法，通知NameNode文件写入成功。



判断失效：





发现DataNode宕机后，NameNode处理时序图，简化表示过程如下：





参考文献：

1 . 对于有环的链表查找是否有合并点，还可以参考如下链接：

https://blog.csdn.net/jiary5201314/article/details/50990349?utm_medium=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase

1. 

https://www.cnblogs.com/testling/p/11581179.html