C++ 9 lines normal solution and 4 lines cheat solution


  • 0

    Normal solution is to use a slow pointer who walk one step forward every time, and a fast pointer who walk two steps forward every time, when they meet, we found a cycle.
    The mechanism of why they are guaranteed to meet can be found here.
    The code is as follows,

        bool hasCycle(ListNode *head) {
            if(!head||!head->next) return false;
            ListNode* slow=head;
            ListNode* fast=head->next->next;
            while(fast&&slow!=fast){
                if(!fast->next) return false;
                slow=slow->next;
                fast=fast->next->next;
            }
            return fast;
        }
    

    The cheat solution needs to modify the linked list but more concise, -1 here can be any integer.

        bool hasCycle(ListNode *head) {
            if(head==NULL) return false;
            if(head->val==-1&&head->next->val==-1) return true;
            head->val=-1;
            return hasCycle(head->next);
        }
    

Log in to reply
 

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