C++ AC solution beats 80% submissions


  • 0
    A
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    private:
        public:
        bool hasCycle(ListNode *head) {
            if(!head) return false;
            ListNode* faster = head->next;
            ListNode* slower = head;
            while(faster && faster->next){
                if(faster == slower) return true;
                faster = faster->next->next;
                slower = slower->next;
            }
            return false;
        }
    public:
        ListNode *detectCycle(ListNode *head) {
            if(!head || !head->next) return NULL;
            ListNode* faster = head->next;
            ListNode* slower = head;
            while(faster && faster->next){
                if(faster == slower) break;
                faster = faster->next->next;
                slower = slower->next;
            }
            if(faster != slower) return NULL;
            if(slower == head) return head;
            ListNode* reacher = head;
            int dist1 = 0, dist2 = 0;
            while(reacher != slower){
                dist1++;
                reacher = reacher->next;
            }
            faster = slower->next;
            while(faster != slower){
                dist2++;
                faster = faster->next;
            }
            faster = slower->next;
            reacher = head;
            while(dist1 > dist2){
                dist1--; 
                reacher = reacher->next;
            }
            while(dist2 > dist1){ 
                dist2--; 
                faster = faster->next;
            }
            while(faster != reacher){
                faster = faster->next; 
                reacher = reacher->next;
            }
            return faster;
        }
    };```

Log in to reply
 

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