如何判断单向链表有环?

前言：链表在开发过程中属于出现频次十分高的一种数据结构，在java中,比如我们熟知的linkedlist、hashmap底层结构、linkedhashmap、aqs等都使用到了链表,关于单向链表有几个经典问题 1:如何判断链表有环  2:如果有环,找出入环的节点 3:环的长度是多少？本篇博客就围绕这三个问题来展开讨论

目录

一:如何判断单向链表有环？

二:如果有环,找出入环的节点

三:环的长度是多少？

四:测试

五:总结

问题一：如何判断单向链表有环？

首先我们来画一个普通的单向链表和环状链表的结构图：

 

 

可以看出在环形单向链表的efgh形成了一个环状,那么如何用程序判断它成环呢？这里要借助一个跑道的思想：假如有一个环形的跑道，跑道上有两个人p和q,假设p的速度是1km/10分钟，q的速度是2km/10分钟,速度恒定不变。如果这个跑道是环型的,他们同时出发,起初q领先,而在某一个时刻，q终将从后面追上过p,他们两一定会相遇,而如果是直线跑道,p和q一定不会相遇。借助于这个思想，我们可以设置快慢指针去绕着环状链表去走，如果两个指针相遇，那么它肯定是环形的。

下面是java版的实现：通过设定两个不同速度的快慢指针来遍历整个链表，如果快慢相遇，则整个链表一定有环：

 

 

 

程序的具体实现:

   /**
     * 链表节点
     */
    public static class node {
        private string value;
        private node next;

        public string getvalue() {
            return value;
        }

        public void setvalue(string value) {
            this.value = value;
        }

        public node getnext() {
            return next;
        }

        public void setnext(node next) {
            this.next = next;
        }
    } 

     /**
     * 链表是否有环
     * @param sourcenode
     * @return
     */
    public static boolean hascircle(node sourcenode) {
        if (sourcenode == null) {
            return false;
        }
        if (sourcenode.next == null) {
            return false;
        }
        //慢指针
        node slowpointer = sourcenode;
        //快指针
        node fastpointer = sourcenode;
        while (fastpointer != null) {

            //慢指针每次一个链表格
            slowpointer = slowpointer.next;
            //快指针每次两个链表格
            fastpointer = fastpointer.next.next;
            if (slowpointer == fastpointer) {
                return true;
            }
        }
        return false;
    }

 

问题二:如果有环,找出入环的节点

   假设环形链表的长度是l,相遇点在m,在相遇之后，只需要将fast指针指向开始的节点，然后和slow指针保持同一的速度遍历(相当于此时不分快慢,每个指针的每次步长为1),下一次两个节点相遇的时候就是链表的环形入口：关于此结论的数学证明：

   

 

 

程序实现如下：

 /**
     * 获取入口节点
     * @param sourcenode
     * @return
     */
    public static node getenternode(node sourcenode) {

        if (sourcenode == null) {
            return null;
        }
        if (sourcenode.next == null) {
            return null;
        }
        //慢指针
        node slowpointer = sourcenode;
        //快指针
        node fastpointer = sourcenode;
        while (fastpointer != null) {
            slowpointer = slowpointer.next;
            fastpointer = fastpointer.next.next;
            if (slowpointer == fastpointer) {
                break;
            }
        }
        system.out.println("相遇点"+fastpointer.getvalue());
        fastpointer = sourcenode;
        while (fastpointer != null) {
            fastpointer = fastpointer.next;
            slowpointer = slowpointer.next;
            if (fastpointer == slowpointer) {
                return fastpointer;
            }
        }
        return null;
    }

 

问题三:环的长度是多少？

   这个问题比较简单，既然我们已经知道了环的入口节点，只需要新增一个指针，顺着环依次循环一遍用一个变量进行累加,每次的步长设为一,然后直到和入口节点相遇(环入口的节点位置保持不变)那么环的长度也就统计出来了:

 

  程序具体实现:

 /**
     * 获取环的长度
     *
     * @param sourcenode
     * @return
     */
    public static int getcirclelength(node sourcenode) {
        if (sourcenode == null) {
            return 0;
        }
        final node enternode = getenternode(sourcenode);
        //环的下一个指针
        node circlesecondnode = enternode.next;
        int lenght = 1;
        while (circlesecondnode != enternode) {
            lenght++;
            circlesecondnode = circlesecondnode.next;
        }
        return lenght;
    }

 

 四：测试

我们来写一个测试方法来模拟一下上面的环状节点，然后测试一下：

public static void main(string[] args) {

        final node node = new node();
        node.setvalue("a");
        final node node2 = new node();
        node2.setvalue("b");
        final node node3 = new node();
        node3.setvalue("c");
        final node node4 = new node();
        node4.setvalue("d");
        final node node5 = new node();
        node5.setvalue("e");
        final node node6 = new node();
        node6.setvalue("f");
        final node node7 = new node();
        node7.setvalue("g");
        final node node8 = new node();
        node8.setvalue("h");
        node.setnext(node2);
        node2.setnext(node3);
        node3.setnext(node4);
        node4.setnext(node5);
        node5.setnext(node6);
        node6.setnext(node7);
        node7.setnext(node8);
        node8.setnext(node5);
        final boolean hascircle = hascircle(node);
        system.out.println("是否是环形链表:"+hascircle);

        final node enternode = getenternode(node);
        system.out.println("相遇节点是:"+enternode.getvalue());

        final int circlelength = getcirclelength(node);
        system.out.println("环状长度:"+circlelength);
        
    }

 

程序输出如下：

 

 五:总结

  本次主要分析了环形链表的一些问题,并给出了示例代码，通过此篇博客可以学习到关于链表的一些东西，快慢指针的基本思想，以及如何求相遇节点和环的长度两个问题，如何用java求解,并熟悉链表这种数据结构，在实际工作中可以加深对环形链表的一些理解。

 

最后: 如果对学习java有兴趣可以加入群:618626589,本群旨在打造无培训广告、无闲聊扯淡、无注水斗图的纯技术交流群，群里每天会分享有价值的问题和学习资料,欢迎各位随时加入