My code:

/**
 * 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)
            return null;
        boolean hasCycle = false;
        ListNode tortoise = head;
        ListNode rabbit = head.next;
        while (rabbit != null) {
            if (rabbit == tortoise) {
                hasCycle = true;
                break;
            }
            rabbit = rabbit.next;
            if (rabbit == null) {
                hasCycle = false;
                break;
            }
            rabbit = rabbit.next;
            tortoise = tortoise.next;
        }
        if (rabbit == null)
            hasCycle = false;
        if (!hasCycle)
            return null;
        ListNode tortoise2 = head;
        rabbit = rabbit.next;
        while (tortoise2 != rabbit) {
            tortoise2 = tortoise2.next;
            rabbit = rabbit.next;
        }
        return rabbit;
    }
}

My test result:

Paste_Image.png

這是一道數(shù)學題。
具體亦鳞，請看這篇博客的解釋。
http://bangbingsyb.blogspot.com/2014/11/leetcode-linked-list-cycle-i-ii.html

然后具體再自己畫一下，移動步數(shù)那一塊兒代碼寫起來有些細節(jié)节腐，如果直接畫一畫外盯，就很容易過了。

**
總結(jié)： 雙指針铜跑， 數(shù)學门怪， List
**

Anyway, Good luck, Richardo!

My code:

/**
 * 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;
        ListNode fast = head;
        boolean hasCycle = false;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next;
            fast = fast.next;
            if (fast == slow) {
                hasCycle = true;
                break;
            }
        }
        if (!hasCycle)
            return null;
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

看了數(shù)學推理，知道了怎么做锅纺，寫出了答案掷空。
我自己沒有推出來。忘記了一個關(guān)鍵點囤锉√沟埽快指針，走的路程是慢指針的兩倍官地。
假設(shè)頭結(jié)點到環(huán)開始處的距離是L, 環(huán)開始處酿傍，到兩個人碰到的地方，距離是X
那么驱入，
2 * (L + X) = L + n * C + X => L = n*C - X
n * C - X 物理意義是赤炒，相遇處到環(huán)開始處的距離。
也就是說亏较，把慢指針放回到起點莺褒。讓快慢指針同時一步一步走。下一次相遇的地方雪情，就是環(huán)開始的地方遵岩。
妙啊。 Fuck, 浪費時間巡通！

Anyway, Good luck, Richardo!

My code:

/**
 * 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;
        ListNode fast = head;
        
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                break;
            }
        }
        
        if (fast.next == null || fast.next.next == null) {
            return null;
        }
        
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        
        return slow;
    }
}

差不多的做法尘执，數(shù)學推導。

Anyway, Good luck, Richardo! -- 08/15/2016