数学解决——环形链表问题

环形链表

 思路：

1. 先通过快慢双指针去遍历链表，直到fast与slow相遇停止（fast的速度必须是slow速度的二倍，不能是三倍、四倍...试想如果环只有两个结点，fast肯定先进环，若后进环slow刚好与fast错开，slow走三倍，fast走两步，是永远不会相遇的！）
2. 再让一个指针从头节点遍历，另一个指针从上一次快慢指针相遇处遍历，两个指针的遍历速度一致必定会在循环的结点入口相遇，想不来？解释如下图：

 代码如下：

public class Solution {
    public ListNode detectCycle(ListNode head) {
                //快指针必须是慢指针速度的二倍
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;
            }
        }
        if(fast == null || fast.next == null){
            return null;
        }
        slow = head;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}