142. Linked List CycleII

NO IMAGE

題目:
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?

解答:

/**
* Definition for singly-linked list.
* class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) return null;
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
//當slow與fast相遇的時候,fast比slow多了一圈,而slow也正好走了一圈。但是slow原來走的是圈外的路,從起點到圈開始的路,所以在實際圈裡剩下的路程,其實就是從起點到圈開始的點的距離。那麼我們設一個點slow2開始從起點走,走到slow2和slow相遇的時候,就是圈開始的點了
if (slow == fast) {
ListNode slow2 = head;
while (slow2 != slow) {
slow2 = slow2.next;
slow = slow.next;
}
return slow;
}
}
return null;
}
}