Run Time Error,why? the last input is a very large sequence........


  • 0
    P

    class Solution {
    public:
    ListNode *detectCycle(ListNode *head) {

    	if(NULL == head || NULL == head->next)return NULL;
    
    	ListNode *p1 = head,*p2 = head->next;
    
    	if(p1 == p2->next)return p1;
    
    	while(NULL != p1 || NULL != p2){
    		if(p1 == p2)break;
    		p1 = p1->next;
    		p2 = p2->next;
    		if(NULL == p2)return NULL;
    		p2 = p2->next;
    	}
    	map<ListNode *,int> m;
    	m.clear();
    	ListNode *collect = p1->next;
    	if(!m.count(p1))m[p1] = 1;
    	while(collect != p1){
    		if(!m.count(collect)){
    			m[collect] = 1;
    		}
    		collect = collect->next;
    	}
    	while(!m.count(head)){
    		head = head->next;
    	}
    	
    	return head;
    
    }
    

    }


  • 0
    L

    I have the same problem and I think my answer should be correct.
    This is my code:
    class Solution {
    public:
    ListNode *detectCycle(ListNode *head) {
    if(!head)
    return NULL;

        ListNode *curr1 = head;
        ListNode *curr2 = head;
        ListNode *curr3 = head;
        while(1){
            if((!curr1-> next)||(!curr2->next->next))
                break;
            curr1 = curr1 -> next;
            curr2 = curr2 -> next -> next;
            if(curr1 == curr2){
                while(1){
                    curr3 = curr3 -> next;
                    curr1 = curr1 -> next;
                    if(curr3 == curr1)
                        return curr3;
                    else
                        continue;
                }
            }
        }
        return NULL;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.