Simple Solution with Explanation (in comments)


  • 0
    C
    /*
     * Approach 
     *      Find the cycle (if any) 
     * 
     *      if (cycle not found)
     *          then return NULL
     *      else
     *          start from head node and check that it can be reached from a node in cycle or not
     * 
     *          if (given node can be reached from cycle node)
     *              then return that node
     *          else
     *              try the same for next node
     * 
     */
    
    
    class Solution {
    public:
        ListNode *detectCycle(ListNode *head) {
            ListNode *slow=head, *fast=head, *first, *cycle;
            
            if (head==NULL || head ->next==NULL) {
                return NULL;
            }
            
            // detect cycle
            while(slow!=NULL && fast!=NULL && fast->next!=NULL) {
                
                slow = slow->next;
                fast = fast->next->next;
                
                if (slow==fast) {
                    break;
                }
            }
            
            // if no cycle found
            if (slow!=fast) {
                return NULL;
            }
            
            
            // for each node check whether it can be reached from cycle node
            // else check for next node
            first = head;
            while (true) {
                cycle = slow->next;
                while (cycle != slow) {
                    if (first == cycle) {
                        break;
                    } else {
                        cycle = cycle->next;
                    }
                }
                
                // if last while loop broke due to first node of cycle, not by complete checking of cycle
                if(first==cycle){
                    break;
                }
                
                // else check for next node
                first = first->next;
            }
            
            // return first node in the cycle
            return first;
        }
    };

Log in to reply
 

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