142. Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
Follow up:
Can you solve it without using extra space?

Solution：快慢指针

思路： step1先看快慢指针是否相遇，若相遇说明有环，则step2再找到环入口
Time Complexity: O(N) Space Complexity: O(1)

屏幕快照 2017-09-07 下午1.20.46.png

Solution Code：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        
        // step1. check if there is a loop
        boolean is_loop = false;
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if(slow == fast) {
                is_loop = true;
                break;
            }
        }
        if(is_loop == false) return null;
        
        // step2. find entry to the loop
        ListNode start = head;
        while(start != slow) {
            start = start.next;
            slow = slow.next;
        }
        return start;
    }
}