LeetCode Linked List Cycle II 和I 通用算法和优化算法

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?

和问题一Linked List Cycle几乎一样。如果用我的之前的解法的话，可以很小修改就可以实现这道算法了。但是如果问题一用优化了的解法的话，那么就不适用于这里了。下面是我给出的解法，可以看得出，这里需要修改很小地方就可以了。 

 

/** 
 * Definition for singly-linked list. 
 * struct ListNode { 
 *     int val; 
 *     ListNode *next; 
 *     ListNode(int x) : val(x), next(NULL) {} 
 * }; 
 */  
class Solution {  
public:  
  
    bool find(ListNode *head, ListNode *testpNode)  
    {  
        ListNode *p = head;  
        while (p != testpNode->next)  
        {  
            if(p == testpNode)  
                return false;  
            p = p->next;  
        }  
        return true;  
    }  
  
  
    ListNode *detectCycle(ListNode *head) {  
        // IMPORTANT: Please reset any member data you declared, as  
        // the same Solution instance will be reused for each test case.  
        if(head == NULL)  
            return false;  
  
        ListNode *cur = head;  
        while(cur != NULL)  
        {  
            if(find(head, cur))  
                return cur->next;  
            cur = cur->next;  
        }  
        return NULL;  
    }  
};  

 

然后转一下下面那位朋友的博客，他的解法很优化，不过只适合第一个LeetCode Linked List Cycle问题，而不适合这里。值得学习学习，一起贴在这里了。

http://blog.csdn.net/doc_sgl/article/details/13614853

 

/** 
 * Definition for singly-linked list. 
 * struct ListNode { 
 *     int val; 
 *     ListNode *next; 
 *     ListNode(int x) : val(x), next(NULL) {} 
 * }; 
 */  
class Solution {  
public:  
    bool hasCycle(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 false;  
            pslow = pslow->next;  
        }while(pfast != pslow);  
        return true;  
    }  
};  

 

 

补充：软件开发 , C++ ,