Linked List Cycle II

来源：Leetcode

原帖：http://oj.leetcode.com/problems/linked-list-cycle-ii/

题目：
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up:
Can you solve it without using extra space?
如果fast pointer是slow pointer的2倍，可以找到相遇点
但是如果fast pointer不是slow pointer的2倍，不能保证一定相遇。

Note:
k: linkedlist length out of cycle
n: cycle length
s: any x times speed
p, q: any integers

n - ((s-1)k % n) + p * n = (s-1) * q
n * (p+1) = (s-1) * q + (s-1) * k % n

s = 3, k = 3, n = 5
5 * (p+1) = 2*q + 1
n * (p+1) = 2 * q + 2 * k % n

代码：

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
     ListNode *detectCycle(ListNode *head) {  
         if (!head || !head->next) return NULL;  
         // {1,2}, tail connects to node {1}, if fast = head->next(不能使用)  
         ListNode *slow = head;  
         ListNode *fast = head;   
         while (fast && fast->next) { // assume cycle exists  
             fast = fast->next->next;  
             slow = slow->next;  
             if (fast == slow) break;  
         }  
         if (slow != fast) {  
             return NULL; // no cycle  
         }  
         fast = head;  
         while (fast != slow) {  
             fast = fast->next;  
             slow = slow->next;  
         }    
         return slow;  
     }  
 };