C++ solution, 14ms


  • 3
    T
    class Solution {
    public:
        ListNode *detectCycle(ListNode *head) {
            if (!head) return NULL;
            ListNode* slow = head;
            ListNode* fast = head;
            while (fast && fast->next) {
                slow = slow->next;
                fast = fast->next->next;
                if (slow == fast) {
                    fast = head;
                    while (slow != fast) {
                        slow = slow->next;
                        fast = fast->next;
                    }
                    return slow;
                }
            }
            return NULL;
        }
    };

  • 0
    E

    I hadn't used this snipppet in my code and it failed the test cases. Could you plz explain what is its use? If slow matches fast haven't we already found the cycle?
    while (slow != fast) {
    slow = slow->next;
    fast = fast->next;
    }


  • 0
    T

    when slow matches fast, we found the cycle point, but the point may not be the start,
    when they met again, the distance they run must follow the equal : fast/slow=x, where x must be an int;


Log in to reply
 

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