Why is this C solution "Time Limit Exceeded"?


  • 0
    V
    /**
     * Make every node points back to its predecessor while iterating forward,
     * so if there is a cycle, it will iterate back to head
     */
    bool hasCycle(struct ListNode *head)
    {
        if (head == NULL || head->next == NULL || head->next->next == NULL)
            return 0;
    
        if (head->next == head || head->next->next == head)
            return 1;
    
        struct ListNode* p1 = head;
        struct ListNode* p2 = p1->next;
        struct ListNode* p3 = p2->next;
    
        while (p3 != NULL && p3 != head) {
            p2->next = p1;
            p1 = p2;
            p2 = p3;
            p3 = p3->next;
        }
    
        return (p3 == head);
    }
    

    Always throws "Time Limit Exceeded" on this test

    [-1,-7,7,-4,19,6,-9,-5,-2,-5]
    tail connects to node index 6
    

    It executes only 0.1ms on tutorialspoint.com online C compiler.


  • 0
    This post is deleted!

  • 0
    V

    @j-j-justwe Please read the comment about how it works.


  • 0
    D

    @vicch7 i do the same thing by python a month ago, and passed all test casts. the faster algorithm is o(n), but this method would be o(2n). maybe it caused the TLE.
    By the way, if you do not want to destroy the List, it's better to inverse it again.


  • 0
    V

    @dyungwang

    If you do not want to destroy the List, it's better to inverse it again.

    Good point. Another reason why this is not the better solution compared with fast/slow pointer.


  • 0
    S

    The solution with 2 pointers gives LTE error. But this solution is correct.

    """
    bool hasCycle(struct ListNode *head) {
    struct ListNode *ptr1 = NULL;
    struct ListNode *ptr2 = NULL;
    bool hasCycle = false;
    if (!head) {
    return false;
    }

    for (ptr1 = head; ; ptr1 = ptr1->next) {
        if (ptr1 == NULL || ptr1->next == NULL || ptr1->next->next == NULL) {
            hasCycle = false;
            break;
        }
        ptr2 = ptr1->next->next;
        if (ptr1 == ptr2) {
            hasCycle = true;
            break;
        }
    }
    
    return hasCycle;
    

    }"""


  • 0
    A

    @selvamani.ramasamy
    ptr1=ptr1->next;
    ptr2=ptr1->next->next;
    in each step, ptr2 only moves 2 more than ptr1,and ptr2 is always 2 step more than ptr1;
    how can u make sure ptr1->next->next==ptr1?


Log in to reply
 

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