小灰算法(一): 快慢指针求解链表是否有环

  Seves

    文章参考自书籍:《漫画算法-小灰的算法之旅》-魏梦舒

    单向有环链表

    如图是一个有环的单向链表,那么我们如何判断一个单向链表有环?会被大家常想到的方法是穷举遍历或者借助一个hashSet来判断。穷举的时间复杂度是O(N*N),借助hashSet的时间复杂度是O(N),空间复杂度是O(N)。

    所以我们今天来介绍一种稍微更优的算法来求解单向链表是否有环。首先我们使用两个指针p1和p2指向链表头结点。然后让p1以速度1向后移动,p2以速度2向后移动。如果两个指针会相遇,则表示此链表有环。

    1. 首先p1和p2指向头结点:

    2. p1一次移动一步到2这个节点,p2一次移动两步到5这个节点

    1. 继续移动

    2. 继续…

    3. 在3这个节点相遇,则表示此链表有环

    为什么这样就能判断链表有环了呢?我们不妨试想一下,如果两个速度不同的人在操场绕圈一直跑,一段时间后速度快的人自然又追上慢的那位了。原因就是因为操场也是个环。这种算法的时间复杂度是O(N),空间复杂度是O(1)。

    1. 接下来我们用代码实现一下
    /**
     * 链表节点
     * @author chenchen
     */
    public class Node {
    
        private int value;
    
        private Node next;
    
        public Node (int value) {
            this.value = value;
        }
    
        public int getValue() {
            return value;
        }
    
        public void setValue(int value) {
            this.value = value;
        }
    
        public Node getNext() {
            return next;
        }
    
        public void setNext(Node next) {
            this.next = next;
        }
    }
    
    
    
    /**
     * 判断一个单向链表是否有环
     * @author chenchen
     */
    public class Test {
    
        public static void main(String[] args) {
            // 1. 创建一个有环单向链表
            Node n1 = new Node(8);
            Node n2 = new Node(2);
            Node n3 = new Node(5);
            Node n4 = new Node(6);
            Node n5 = new Node(3);
            Node n6 = new Node(9);
            Node n7 = new Node(7);
    
            n1.setNext(n2);
            n2.setNext(n3);
            n3.setNext(n4);
            n4.setNext(n5);
            n5.setNext(n6);
            n6.setNext(n7);
            n7.setNext(n4);
    
            // 2. 判断是否有环
            boolean result = isLoopLink(n1);
            System.out.println(result);
    
        }
    
        /**
         * 判断此单向链表是否有环
         * @param head Node
         * @return boolean
         */
        private static boolean isLoopLink(Node head) {
            // 1. p1,p2指向头结点
            Node p1 = head;
            Node p2 = head;
    
            // 2. p1和p2以不同的速度向后移动
            while (null != p1 && null != p2.getNext()) {
                p1 = p1.getNext();
                p2 = p2.getNext().getNext();
                if (p1 == p2) {
                    return true;
                }
            }
            return false;
        }
    
    }
    
    

    单向有环链表
    很明显,咱这个环的长度是4,入环的节点是6. 所以有了下面两个扩展问题大家来思考一下。
    7. 扩展一:如何求出环的长度
    思路:首次相遇后,p2和p1继续移动,下次相遇时p2比p1整整多跑了一圈。所以环长=速度差*前进次数

    1. 扩展二:如何求出入环节点

    如图,我们假设头结点到入环点的距离是D, 入环点到首次相遇点的距离是s1, 首次相遇点继续往后走再回到入环点的距离是s2. 那么两指针首次相遇时各走了多少距离呢。
    p1:D+S1
    p2: D+S1+S2+S1
    因为p2速度是p1的二倍,所以有
    2(D+S1) = D+S1+S2+S1
    整理得到: D = S2
    有了这个结论那么我们将p1重置回头结点,p2在首次相遇点。两个指针都是每次移动一步,这样再次相遇时就是入环点了。

    作者 [@没有故事的老大爷][1]
    [1]: https://www.chenchen.zone/

    37