My C++ Solution within O(n) time-complexity and O(1) space-complexity


  • -1
    V
    class Solution {
    public:
        bool hasCycle(ListNode *head) {
            ListNode *destination = new ListNode(0);
             
            while (head != NULL) {
                ListNode *tmp_next = head->next;
                 
                if (tmp_next == destination) return true;
                else head->next = destination;
                 
                head = tmp_next;;
            }
             
            return false;
        }
    };
    

    My idea is similar with the guy who set the special number, but I think my solution may be a better one.


  • 0
    G

    I like your answer but why do you need to allocate a new destination node ? you only need the pointer, don't you ?


  • 1
    G

    class Solution {
    public:
    bool hasCycle(ListNode *head) {

        ListNode *p = head;
        ListNode *q = head;
    
        while(q && q->next)
        {
            p = p->next;
            q = q->next->next;
            
            if (p == q)
                return true;
                
        }
        return false;
        
        
    }
    

    };


  • 0
    G

    The idea on my solution is that you have 2 pointers. One of them(q) advances by steps of 2 and one of them advances by steps of 1. if there is a cycle, they will be the same at some point. There is no need to modify the list with a magic number.


  • 0
    S

    @guasend,
    Pay attention to "Writing code? Select all code block then click on the {} button to preserve code formatting.” above text editor.


Log in to reply
 

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