算法__判断链表中是否有环,并找入环对象

链表:是不基于物理连接的列表,是靠前对象引用后边对象组成一串对象。(如下)

  《算法__判断链表中是否有环,并找入环对象》   

 链表中出现了环,就是我们中的最后一个引用又指回了链中的一个对象。(如下)

《算法__判断链表中是否有环,并找入环对象》

 我们就是想判断出链表中是否有环,不判断的话,我们就可能在取链中数据时进入死循环。

 该如何判断这个列表中是否有环,只要我们判断在这个链子是否有相同的指向。也就是两个对象的next指的对象一样。

 先写个对象

public class NodeVo {

    NodeVo next;

    public NodeVo getNext() {
        return next;
    }

    public void setNext(NodeVo next) {
        this.next = next;
    }
}

 用两个指针,在链表上循环。每循环一次,一个指针走两格,一个走一格。如果有环的话最终两个对象会相同。就好像,我们在操场跑步一样,只要我们在绕着环行跑道跑,跑的快的一定会追上跑的慢的。这样我们减少了,一个对象循环对比整个链上对象的尴尬。

 首先:我们必须知道如果链表中出现null,说明一定没有环。所有判断有环的代码如下

public boolean glp(NodeVo nodeVo) {
   NodeVo fast = nodeVo, low = nodeVo;

   while (fast.getNext() != null && low.getNext().getNext() != null){
            fast=fast.getNext();
            low=low.getNext().getNext();

            if(fast==low)
                break;

        }

        if(fast==null||low==null)
            return false;
        
        return true;
    }

那如何找环的入口呢?(进入函数课程—啦啦啦!!!开心不?)

设low的路程为  S,

 fast的路程则为 2S,

 环的长度为  R,

 链表开始到环口  A,

 环口到遇到的长度为 X,

 那么  S=A+X,

          2S=S+nR,     (n fast可能已经在环中转了几圈,low才进圈)

          A+X=(n-1)R+L-A;

          A=(n-1)R+L-X-A;

 所以,假设我们的n=1,首节点到入口点的长度等于相交点到入口点的距离。所以,我们找两个对象分别从首节点和相交点开始走,每次走一格。相遇的就是相交点。


    public NodeVo getNode(NodeVo nodeVo1, NodeVo nodeVo2) {

        while (nodeVo1 != nodeVo2) {
            nodeVo1 = nodeVo1.getNext();
            nodeVo2 = nodeVo2.getNext();
        }

        return nodeVo1;

    }

 

    原文作者:张康瑞
    原文地址: https://blog.csdn.net/KKnick1/article/details/99443324
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞