package suanfa.list;

import java.util.List;
//快慢指针 慢指针一次走一个,快指针每次走两个,如果有环 则一定会出现 slow==fast
public class HasCycle {

public static void main(String[] args) {

    ListNode head = new ListNode();
    ListNode node2 = new ListNode();
    ListNode node3 = new ListNode();
    ListNode node4 = new ListNode();
    ListNode node5 = new ListNode();
    ListNode node6 = new ListNode();

    head.setVal(1);
    node2.setVal(2);
    node3.setVal(3);
    node4.setVal(4);
    node5.setVal(5);
    node6.setVal(6);

    head.setNext(node2);
    node2.setNext(node3);
    node3.setNext(node4);
    node4.setNext(node5);
    node5.setNext(node6);
    node6.setNext(node3);

    System.out.println(hasCycle(head));
}

public static Boolean hasCycle(ListNode head) {

    if (head == null) {
        return Boolean.FALSE;
    }

    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return Boolean.TRUE;
        }
    }
    return Boolean.FALSE;
}

static class ListNode {

    int val;
    ListNode next;

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public ListNode getNext() {
        return next;
    }

    public void setNext(ListNode next) {
        this.next = next;
    }
}

}