package com.zmz.algorithm.listnode;

/**
 * @author 张明泽
 * Create by 2022/5/29 21:23
 * 环形链表II
 * LeetCode-142
 */
public class CircularListNode {
    public static void main(String[] args) {
        ListNode head = new ListNode(3);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(0);
        ListNode node4 = new ListNode(4);
        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2;
        ListNode result = circular(head);
        traverse(result);
    }

    /**
     * 慢指针走 1 个单位,快指针走 2 个单位,他们一定在环内相遇
     * 相遇以后 将一个指针恢复原来 快慢指针同时走一个单位 相遇时就是入口点
     * 公式： x 为起点到入口点, y 为入口点到相遇点, z 为相遇点到入口点
     * 设慢指针从起点到相遇的距离 x + y,快指针从起点到相遇的距离 2(x + y) = x + y + n(y + z) -> x + y = n(y + z) -> x = (n - 1)(y + z) + z
     */
    public static ListNode circular(ListNode listNode) {
        ListNode fast = listNode;
        ListNode slow = listNode;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                fast = listNode;
                while (fast != slow) {
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            }
        }
        return null;
    }
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    public static void traverse(ListNode listNode) {
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }
}