当前位置 博文首页 > 是琳琳呀!的博客:判断一个链表是否有回环返回第一个回环节点

    是琳琳呀!的博客:判断一个链表是否有回环返回第一个回环节点

    作者:[db:作者] 时间:2021-08-27 16:06

    定义一个快慢指针,快指针一次走两步,慢指针一次走一步,进入循环,此时结束循环有两种情况,一种是没有环,一种是当快慢指针相遇时,结束循环。因为快指针是慢指针的两倍,则当二指针相遇时快指针走了慢指针的两倍,设进入环时的路程为X,慢指针进入环后走了L,即当二人相遇时,快指针又走了X+2L的路程,则快指针在离入环点环还有X.

    public Node theListNode(){
    if(headnull){
    return null;
    }
    Node fast=this.head;
    Node slow=this.head;
    while(fast!=null&&fast.next!=null){
    fast=fast.next.next;
    slow=slow.next;
    if(fast
    slow){
    break;
    }
    }
    if(fastnull||fast.nextnull) {
    return null;
    }
    slow=this.head;
    while(fast!=slow){
    fast=fast.next;
    slow=slow.next;
    }
    return slow;
    }

    cs