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;
                if(!fast->next) return false;
            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;
            return hasCycle(head->next);

Log in to reply

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