Leetcode: Linked List Cycle II - c++编程基础

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

/** 
 * 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) {  
        // IMPORTANT: Please reset any member data you declared, as  
        // the same Solution instance will be reused for each test case.  
        ListNode* pfast = head;  
        ListNode* pslow = head;  
        do{  
            if(pfast != NULL)  
                pfast = pfast->




next;  
            if(pfast != NULL)  
                pfast = pfast->next;  
            if(pfast == NULL)  
                return pfast;  
            pslow = pslow->next;  
        }while(pfast != pslow);  
        pfast = head;  
        while(pfast != pslow)  
        {  
            pfast = pfast->next;  
            pslow = pslow->next;  
        }  
        return pfast;  
    }  
};