/** * Source : https://oj.leetcode.com/problems/linked-list-cycle-ii/ * * Given a linked list, return the node where the cycle begins. If there is no cycle, return null. * * Follow up: * Can you solve it without using extra space? */public class LinkedListCycle2 {    /**     * 如果链表是循环的，则找到循环的开始节点     * 否则，返回null     *     * 依然使用双指针法，如果是循环链表的话，     * slow和fast第一次相遇之后，将slow = head，     * 然后将slow和fast每次移动一个节点，第二次相遇的时候就是循环的起始节点     *     * 原理：     * 假设head到start的距离a，slow和fast第一次相遇的位置距离start为b，循环链表周长为c，第一次相遇的时候fast走过的长度一定是slow的两倍，在过程中遍历了循环链表n次     * (a + b) * 2 = a + n * c + b     * 那么a = n*c - b => a + b = n*c     * 也就是说，现在让两个指针slow指向head，fast指向第一次相遇的位置，然后每次两个指针移动一个节点，直到下一次相遇，正好走过n个周长，即下一次相遇在start位置     *     * @param head     * @return     */    public LinkedNode findCycleStart (LinkedNode head) {        if (head == null) {            return null;        }        LinkedNode slow = head;        LinkedNode fast = head;        while (fast.next != null && fast.next.next != null) {            slow = slow.next;            fast = fast.next.next;            if (slow == fast) {                break;            }        }        if (fast == slow) {            // 链表存在循环            slow = head;            while (slow != fast) {                slow = slow.next;                fast = fast.next;            }            return slow;        }        return null;    }    private class LinkedNode {        int value;        LinkedNode next;    }    /**     * 创建普通的链表     * @param arr     * @return     */    public LinkedNode createList (int[] arr) {        if (arr.length == 0) {            return null;        }        LinkedNode head = new LinkedNode();        head.value = arr[0];        LinkedNode pointer = head;        for (int i = 1; i < arr.length; i++) {            LinkedNode node = new LinkedNode();            node.value = arr[i];            pointer.next = node;            pointer = pointer.next;        }        return head;    }    /**     * 将链表变为循环链表，循环起始为第index个node     * @param head     * @param index     */    public void makeCycle (LinkedNode head, int index) {        if (head == null) {            return;        }        LinkedNode tail = head;        int count = 1;        while (tail.next != null) {            tail = tail.next;            count++;        }        LinkedNode p = head;        if (index > count) {            index = index % count;        } else if (index < 0) {            index = Math.abs(index);        }        while (p != null) {            index--;            if (index < 1) {                tail.next = p;                break;            }            p = p.next;        }    }    public static void main(String[] args) {        LinkedListCycle2 linkedListCycle = new LinkedListCycle2();        LinkedNode list = linkedListCycle.createList(new int[]{1,2,3,4,5});        System.out.println(linkedListCycle.findCycleStart(list) + " == null");        linkedListCycle.makeCycle(list, 2);        System.out.println(linkedListCycle.findCycleStart(list).value + " == 2");    }}