带环链表 II

给定一个链表，如果链表中存在环，则返回到链表中环的起始节点的值，如果没有环，返回null。

思路详解

• leetcode
• [链表]环和起点
• 经典面试题：链表的相交与环问题

class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: The node where the cycle begins. 
     *           if there is no cycle, return null
     */
    ListNode *detectCycle(ListNode *head) {
        // write your code here
        if (!head || !head->next) {
            return NULL;
        }
        
        ListNode *fast = head;
        ListNode *slow = head;
        
        while(fast->next && fast->next->next) {
            fast = fast->next->next;
            slow = slow->next;
            
            if(fast == slow) {
                ListNode *temp = head;
                while(fast != temp) {
                    temp = temp->next;
                    fast = fast->next;
                }
                return fast;
            } 
        }
      
        
        return NULL;
    }
};