写点什么

作业 --week08

用户头像
张荣召
关注
发布于: 2020 年 11 月 16 日

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 的处理过程时序图。



用户头像

张荣召

关注

还未添加个人签名 2018.05.02 加入

还未添加个人简介

评论

发布
暂无评论
作业--week08