package NC;

/**
 * NC4 判断链表中是否有环
 *
 * 描述
 * 判断给定的链表中是否有环。如果有环则返回true，否则返回false。
 * (头尾相接为环，尾和链中任意节点相接也可以连成环)
 *
 * 数据范围：链表长度 ，链表中任意节点的值满足
 * 要求：空间复杂度O(1) ，时间复杂度O(N)
 *
 *
 * @author Tang
 * @date 2021/9/26
 */
public class HasCycle {

    /**
     * 利用快慢指针是否相遇判断
     *
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) {
            return false;
        }
        ListNode index1 = head.next;
        ListNode index2 = head.next.next;
        while(index1 != null && index2 != null && index2.next != null) {
            if(index1 == index2) {
                return true;
            }
            index1 = index1.next;
            index2 = index2.next.next;
        }

        return false;

    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        node1.next = node2;
        node2.next = node3;
        node3.next = node1;
        new HasCycle().hasCycle(node1);

    }

}