My 12ms c++ solution without extra space


  • 2
    X
    class Solution {
    public:
    bool hasCycle(ListNode *head) {
        
        // the first pointer 
        ListNode *pt_f=head;       
        if(pt_f==nullptr)
           return false;
           
        // the second pointer 
        ListNode *pt_s=head->next;
        if(pt_s==nullptr)
           return false;
        
        // the 2rd pointer go firstly, if it arrived the end of the list, return false
        // if it catchs the first pointer, return ture
        // the 2rd pointer move twice the steps than the 1st pointer
        
        int step=1;
        while(1){
           for(int i=0;i<2*step;i++){
               pt_s=pt_s->next;
               if(pt_s==pt_f)
                  return true;
               if(pt_s==nullptr)
                  return false;
           }
           for(int j=0;j<step;j++)
               pt_f=pt_f->next;
           
           step++;
           
        }
        
       return false;
        
    }
    
    };

  • 0
    S

    good job!but I dont't understand why 2rd can catch 1rd if circle exists.


  • 0
    S

    The sentences in while loop will always run, so why "return false;" in the last?


Log in to reply
 

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