欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

单链表的环问题以及相交问题

程序员文章站 2022-06-06 13:39:37
...

1.求单链表是否有环?若有环,求环的入口点以及环的长度。

流程:创建一个有环的单链表——->
单链表的环问题以及相交问题
先判断是否有环:

public boolean isLoop(){
        Entry fast = head;//走得快的结点
        Entry slow = head;//走得慢的结点
        while(fast != null && fast.next != null){
            fast = fast.next.next;//快的两步走
            slow = slow.next;//慢的一步走
            if(fast == slow){//快的和慢的相遇则证明有环
                return true;
            }
        }
        return false;//否则没环
    }

假若此时单链表有环,求环的入口点:

public int getEntryLoop(){
        if(!isLoop()){//为保证稳定性,先判断是否有环
            return -1;
        }
        Entry fast = head;
        Entry slow = head;
        //先找到相遇点
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;
            }
        }
        slow = head;//找到相遇点之后使任意一个回到头结点位置
        //使两个节点接着一步一步走直到相等,如图所示,两段距离均为x,此时的结点就是入口点
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return slow.data;
    }

求环的长度:

public int getLengthLoop(){//看图可知环的长度就是相遇后的X加上相遇前的Y
        int len = 0;
        Entry fast = head;
        Entry slow = head;
        boolean tag = false;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow && tag == true){//第二次相遇
                break;
            }
            if(fast == slow && tag == false){//第一次相遇
                tag = true;
            }
            if(tag = true){
                len++;
            }
        }
        return len;
    }

2.求两个单链表是否相交?若相交,求交点。

单链表的环问题以及相交问题
判断是否相交:

    public boolean isCut(TestLink t1,TestLink t2){
        TestLink.Entry head1 = t1.getHead();
        TestLink.Entry head2 = t2.getHead();
        int len1 = t1.getLength(); 
        int len2 = t2.getLength();
        int my_len = len1-len2;
        if(my_len<0){//寻找最长的单链表,并且使head1指向最长的单链表
            head1 = t2.getHead();
            head2 = t1.getHead();
        }
        for(int i =0;i<my_len;i++){//使最长单链表走到和另外一个单链表同样的位置(如图的起跑线)
            head1 = head1.next;
        }
        //然后同时一步一步走(如图从起跑线同时走)
        while(head1 != null && head2 != null && head1 != head2){
            head1 = head1.next;
            head2 = head2.next;
        }
        //如果有某一处两个节点相同,则相交,否则不相交(寻找是否有如图的交点)
        if(head1 == head2 && head1 != null && head2 != null){
            return true;
        }else{
            return false;
        }
    }

求交点:

    public int cutPoint(TestLink t1,TestLink t2){
        TestLink.Entry head1 = t1.getHead();
        TestLink.Entry head2 = t2.getHead();
        int len1 = t1.getLength(); 
        int len2 = t2.getLength();
        int my_len = len1-len2;
        if(my_len<0){//使head1指向最长的单链表
            head1 = t2.getHead();
            head2 = t1.getHead();
        }
        for(int i =0;i<my_len;i++){//使最长单链表走到和另外一个单链表同样的位置
            head1 = head1.next;
        }
        //然后同时一步一步走
        while(head1 != null && head2 != null && head1 != head2){
            head1 = head1.next;
            head2 = head2.next;
        }
        //如果有某一处两个节点相同,则相交,则输出值就是交点的值
        if(head1 == head2 && head1 != null && head2 != null){
            return head1.data;
        }else{
            return -1;
        }
    }

求交点值只是在判断有相交之后加上输出就实现了!!!

相关标签: 单链表