AC solution with O(1) space and O(n) time in C++


  • 9
    T
    class Solution {
    public:
    bool hasCycle(ListNode *head) {
        if(!head||!head->next)
            return false;
        ListNode* i = head; //slower pointer
        ListNode* j = i->next; //faster pointer
        while(i&&j&&j->next)
        {
            i = i->next;
            j = j->next->next;
            if(i==j)
                return true;
        }
        return false;
    }
    };

  • 6
    C

    You really don't need the initial test for

    if(!head||!head->next)
        return false;
    

    I it is handled in the while loop body. Here is my accepted code.

        bool hasCycle(ListNode *head) {
        ListNode *p1= head, *p2= head;
        while (p1 && p2 && p2->next) {
            p1 = p1->next;
            p2 = p2->next->next;
            if (p1==p2) return true;
        }
        return false;
    }
    

Log in to reply
 

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