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;
}
}
