链表中环的入口结点

详细证明

public class EnterCycleNode {

public static ListNode findEntryNode(ListNode head){
    if(head == null || head.next == null){
        return null;
    }
    ListNode slow = head;
    ListNode fast = head;
    slow = slow.next;
    fast = fast.next.next;
    while (fast != null && fast.next != null){
        if(slow == fast)
            break;
        slow = slow.next;//这里两步的顺序不能反保证fast走过距离是slow的倍数
        fast = fast.next.next;
    }
    if(slow != fast){//无环
        return null;
    }

    //走到这说明有环
    slow = head;
    while (slow != fast){
        slow = slow.next;
        fast = fast.next;
    }

    return slow;
}
public static void main(String[] args){
    Link link = new Link();
    link.add(1);
    link.add(2);
    link.add(3);
    link.add(4);
    ListNode tail = link.head;
    while (tail.next != null){
        tail = tail.next;
    }
    tail.next = link.head.next;
    System.out.println(EnterCycleNode.findEntryNode(link.head).data);
}
}