4ms c solution based in pointers-meeting idea


  • 2
    5
     typedef  struct ListNode ListNode;
    

    bool hasCycle(struct ListNode *head) {

    ListNode* pslow ,*pfast;
    pslow = pfast = head;
    
    while( pslow&&pfast){
        pslow = pslow->next;
        if(pfast->next){
            pfast = pfast->next;
            pfast = pfast->next; 
        }else {
         pfast = pfast->next;
         break;   
        }
      
        if(pfast == pslow)break;
        
    }
    if(  !pslow||!pfast)return false;
    return true;
    

    }

    The main idea is that a slow pointer moving one step while a fast pointer moving two steps from a same start point, but they will meet at the same positon if there is any cycle.


  • -1
    B

    that's a wrong idea.
    if the cycle has even nodes and the distance of fastnode and the slownode when slow one gets into cycle is even, these two pointers will never meet each other!!!


  • 0
    H

    I don't think so. The fast pointer move two steps and the slow one move one. Each time they move their distance decreases by one. No matter the distance is even or odd, it will decreases one by one till zero. Then they will meet. This is a proved method. No need to argue on that.


Log in to reply
 

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