JAVA学习记录--单链表问题

问题1:输入两个链表,找出它们的第一个公共节点

问题2:将两个升序链表合成一个升序链表并返回,新链表是通过拼接给定的两个链表的所有节点组成的

   /*输入两个链表,找出它们的第一个公共节点
    如果两个链表的长度不一样,定义两个链表的头节点分别为pl(较长的链表),ps(较短的链表),
    先计算两个链表的长度,得到的△,让较长的链表pl先走△个节点,与较短的链表ps长度相同时,
    以同等速度向后走,当pl.next=ps.next,即为第一个公共节点
    * */
     public static Node getIntersectionNode(Node headA,Node headB){
        int lenA=0;
        int lenB=0;
        Node pl=headA;
        Node ps=headB;
        while(pl!=null){
            pl=pl.next;
            lenA++;
        }
        while (ps!=null){
            ps=ps.next;
            lenB++;
        }
        int len=lenA-lenB;
        if(len<0){
            pl=headB;
            ps=headA;
            len=lenB-lenA;
        }else{
            pl=headA;
            ps=headB;
        }
        for(int i=0;i<len;i++){
            pl=pl.next;
        }
        while(pl!=ps&&pl!=null&&ps!=null){
            ps=ps.next;
            pl=pl.next;
        }
        if(pl==ps&&pl!=null&&ps!=null){
            return pl;
        }
            return null;
    }

    /*将两个升序链表合成一个升序链表并返回,新链表是通过拼接给定的两个链表的所有节点组成的
    定义了一个傀儡节点newHead来保存新链表第一个节点,tmp是从newHead开始,来收集新链表升序的引用,
    可以把tmp看做“墙头草”,哪边小往哪边倒。
     */
    public Node nergeTwolists(Node headA,Node headB){
         Node newHead=new Node(-1);
         Node tmp=newHead;
         while (headA!=null&&headB!=null){
             if(headA.data<headB.data){
                 tmp.next=headA;
                 headA=headA.next;
                 tmp=tmp.next;
             }else {
                 tmp.next=headB;
                 headB=headB.next;
                 tmp=tmp.next;
             }
         }
         if(headA!=null){
             tmp.next=headA;
         }
         if(headB!=null){
             tmp.next=headB;
         }
         return newHead.next;
    }

上一篇:Windows 终端中设置 Powerline


下一篇:TC查询 锁定的账户进程id