Accepted O(1) space solution through reverse List


  • 0
    L
    bool hasCycle(ListNode *head)
    {
        //reverse link list reverse
        ListNode *prev,*cur,*next;
        ListNode dummy(0);//create a head node ,if cycle exists,it will return head after reverse
        prev = &dummy;
        cur = head;
        while(cur)
        {
            if(cur == &dummy)
            return true;
            
            next = cur ->next;
            cur -> next = prev;
            prev = cur;
            cur = next;
        }
        return false;
    }
    

    1,create a head node
    2,reverse the list,if a cycle exists,it wii meet the head node again.


Log in to reply
 

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