version at 2022-04-19

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

/**
1. O(1)空间不能辅助记录 -> 查看步长
2. 还是使用快慢指针, 快指针每次走2步 没有环的时候可以遍历到null, 有环必定相交
3. 令头节点到环起始点的长度x = len(head->start), 环起始点到交点的长度为y = len(start -> intersect)
4. 在相交时, 慢节点走过了 x+y 距离, 快指针走了 2(x+y)
            因为慢指针到达start时, 快指针已经在环上走了x步
            慢指针到达交点时, 快指针又走了 2y步
            因为到达交点必定快指针在环上多走了一圈, 所以环的长度为 x+y
            那也就是说此时慢指针在环上再走x步就回到起始点start了

*/

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode a = head, b = head;

        do {
            if (b == null) return null;
            b = b.next;
            if (b == null) return null;
            b = b.next;

            if (a == null) return null;
            a = a.next;
        } while (a != b);

        b = head;
        while (a != b) {
            a = a.next;
            b = b.next;
        }

        return a;
    }
}

version at: 2020-02-02

/*
1. 无法记录状态，想下步长和遍历 -> 制造2个指针相遇 -> 快慢指针，快指针先入环多走, 快指针走2步
2. 当slow 到达交点：      slow 走了x步，  fast走了2x步
   当slow 和 fast 相交：  slow 走了x+y步，fast走了2x+2y步， 位置相同 -> 环的长度为 x+y
    此时fast离环的起点距离为 x，所以让slow再从头走一遍即可

3. testcase：环离表头的距离：0，1，2，3； 无环； 链表长度：0，1，2，3
*/

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) return null;

        var slow = head.next;
        var fast = head.next.next;

        while (slow != fast){
            if (fast == null) return null;
            fast = fast.next;
            if (fast == null) return null;
            fast = fast.next;
            slow = slow.next;
        }
        slow = head;
        while (slow != fast){
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }
}