作业 --week08

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

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

解析：伪代码

   假设链表1： Node head1=new Node(data,next);

          链表2： Node head2=new Node(data,next);

   算法1: 双重循环。时间复杂度O(n^2)

   public  class Test{

         public static Node testJoinPoint(Node header1,Node header2){

               Node pointer1=header1;

               Node pointer2=header2;

               while(pointer1.getNext()!=null){

                     while(pointer2.getNext()!=null){

                            if(pointer1.getNext()==pointer2.getNext()){

                                  return pointer2;

                            }else{

                               pointer2=pointer2.getNext(); 

                            }

                     }

                     pointer1=pointer1.getnext();

               }

         }

         public static void main(){

              Node node=testJoinPointer(head1,head2);

              System.out.println("交差点："+node.value);

         }

    }    

算法2: 借助2个栈，对比栈顶元素是否相等。利用空间换时间。时间复杂度O(n)

  public  class Test{

         public static Node testJoinPoint(Node header1,Node header2){

               Stack<Node> stack1=linkedListToStack(header1);

               Stack<Node> stack2=linkedListToStack(header2);

               Node joinPointer=null;

               while(!stack1.empty()&&!stack2.empty()){

                     Node pointer1=stack1.pop();

                     Node pointer2=stack2.pop();

                     if(pointer1==pointer2){

                           joinPointer=pointer1; 

                     }else{

                           break;

                     }     

               } 

         }

         public static Stack<Node> linkedListToStack(Node head1){

                Stack<Node> stackForList=new Stack<Node>();

                 for(Node  pointer=head1.getNext();pointer!=null;pointer=hea1.getNext()){

                      stackForList.push(pointer);

                 }

                 return stackForList;

         }



         public static void main(){

              Node node=testJoinPointer(head1,head2);

              System.out.println("交差点："+node.value);

         }

    }

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