142.环形链表-ii

设slow从head走到环起始点a步, 从head走到相遇点走了b步, 环长c步 设fast比slow多走了k圈, 2b - b = kc => b = kc; slow在环中走了b - a步, 即走了kc - a步, 所以slow再走a步就能到达环起点

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}
// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    /**
     * 设slow从head走到环起始点a步, 从head走到相遇点走了b步, 环长c步
     * 设fast比slow多走了k圈, 2b - b = kc => b = kc;
     * slow在环中走了b - a步, 即走了kc - a步, 所以slow再走a步就能到达环起点
     */
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) break;
        }
        if (fast == null || fast.next == null) return null;
        while (head != slow) {
            head = head.next;
            slow = slow.next;
        }
        return head;
    }
}