本文共 3082 字，大约阅读时间需要 10 分钟。

public class LinkedHasCycle {    /**     * 判断是否有环：如果跑道是环形的，一块一慢必然相遇     * 时间复杂度 O(n)     * 空间复杂度O(1),除了两个指针外没有使用其他额外存储空间     *     * @param node     * @return     */    public static boolean hasCycle(Node node) {        Node p1 = node;        Node p2 = node;        while (p1 != null && p2.next != null) {            p1 = p1.next;            p2 = p2.next.next;            if (p1 == p2) {                return true;            }        }        return false;    }    /**     * 求环长度：     * 当链表有环后两指针继续向前循环，当再次相遇后即环的长度 环长 = 每次速度差 * 前进次数 = 前进次数     *     * @param node     * @return     */    public static int cycleLength(Node node) {        Node p1 = node;        Node p2 = node;        boolean hasCycle = false;        int cycleLength = 0;        while (p1 != null && p2.next != null) {            p1 = p1.next;            p2 = p2.next.next;            if (p1 == p2) {                if (hasCycle) {                    break;                }                hasCycle = true;            }            if (hasCycle) {                cycleLength++;            }        }        return cycleLength;    }    /**     * 求入环点：     * 链表头节点到入环点的距离，等于从首次相遇点环绕n-1圈后再回到入环点的距离。     * 保持节点在首次相遇点，另一个指针回到头节点位置，两个指针都每次向前走一步，那么最终相遇的节点，就入环节点     * @param node     * @return     */    public static Node getInsertCycleNode(Node node) {        Node original = node;        Node p1 = node;        Node p2 = node;        //相遇节点        Node p3 = null;        while (p1 != null && p2.next != null) {            p1 = p1.next;            p2 = p2.next.next;            //两者相遇时，退出，p1节点就是两者相遇的节点            if (p1 == p2) {                p3 = p1;                break;            }        }        //保持节点在首次相遇点，另一个指针回到头节点位置，两个指针都每次向前走一步，那么最终相遇的节点，就入环节点        while (original != null && p3 != null) {            original = original.next;            p3 = p3.next;            if (original == p3) {                return original;            }        }        return null;    }    private static class Node {        private Integer data;        private Node next;        Node(Integer data) {            this.data = data;        }        @Override        public String toString() {            return this.data + "";        }    }    public static void main(String[] args) {        Node node1 = new Node(5);        Node node2 = new Node(3);        Node node3 = new Node(7);        Node node4 = new Node(2);        Node node5 = new Node(6);        node1.next = node2;        node2.next = node3;        node3.next = node4;        node4.next = node5;        node5.next = node2;        System.out.println("是否有环：" + hasCycle(node1));        System.out.println("环长度：" + cycleLength(node1));        System.out.println("当前入环节点为:" + getInsertCycleNode(node1));    }}

针对入环点方法 getInsertCycleNode 说明：

假设从链表头节点到入环点的距离是D，从入环点到首次相遇节点距离是S1，从首次相遇到入环点的距离是S2

那么当两次首次相遇时：

指针p1，一次只走一步，所走的距离是D+S1

指针P2，一次走两步，多走了n(n>=1)整圈，所走的距离是D+S1+n(S1+S2)

由于p2的速度是p1的2倍，所以所走的距离也是p1的两倍，因此：

2(D + S1) = D + S1 + n(S1 + S2)  -->  D =(n -1)(S1 + S2) +S2;

也就是说，从链表头节点到入环点的距离，等于从首次相遇点绕环 n-1圈再回到入环点的距离

所以只要把其中一个指针放回到头节点位置，另一个指针保持在首次相遇点，两个指针都向前走一步，那么他们最终相遇的节点就是入环点。

转载地址：http://iqsvi.baihongyu.com/