C++ TLE problem (I think it is the same as the previous one "I can‘t find the following code has problems.")


  • 0
    D

    I understand there is a fast/slow pointer solution, which can give a O(n) time solution (my version is included at the end).
    There is another O(n^2) time solution, which I think is also correct. But my version got a TLE error. Any comments on why?
    The basic idea is to check if a node's next node precedes or is equal to itself. If no such node found, then no loop. So for each node in the list, the following algorithm checks from the head to itself to see if its next node appears before itself.

    // NEXT NODE CHECKING SOLUTION
           bool hasCycle(ListNode *head) {
                ListNode *curNode, *nextNode, *tempNode;
                
                curNode  = head;
                while(curNode)
                {
                    nextNode = curNode->next;
                    for(tempNode = head;  (tempNode!=nextNode) && (tempNode!=curNode); tempNode = tempNode->next);
                    if(tempNode == nextNode)
                    {
                        return true;
                    }
                    curNode = nextNode;
                }
                return false;
            }        
        
         // FAST/SLOW POINTER SOLUTION  
         bool hasCycle(ListNode *head) {
                
                    ListNode *fastNode, *slowNode;
                    fastNode  = slowNode = head;
                    while(fastNode && fastNode->next)
                    {
                        fastNode = (fastNode->next)->next;
                        slowNode =slowNode->next;
                        if(fastNode == slowNode)
                            return true;
                    }
                    return false;
            }

  • 0
    A

    for(tempNode = head; (tempNode!=nextNode) && (tempNode!=curNode); tempNode = tempNode->next);
    this you will hava a endless loop


  • 0
    D

    Could you please elaborate why? I still can not see why that is the case (endless loop) since it will stop either at curNode (no loop between head and curNode if curNode and nextNode are different, or self-looped where curNode == nextNode) or before curNode (loop found)


  • 0
    A

    when you enter this"while(curNode)" when the nextNode and curNode are not in the cycle,
    the tempNode will not equal nextNode neither curNode


Log in to reply
 

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