I reckon I would not be able to devise such solution in an interview


  • 0
    A

    Whoever can in interview without knowing the algorithm beforehand must be a genuine genius.

    // v = 1: slow pointer speed
    // V = 2: fast pointer speed
    // c: circle length
    // a: length from head to circle entry
    // b: length from circle entry to where they meet
    // slow pointer distance d = vt = a+b
    // (because fast must have caught up with slow before slow can finish even one lap.)
    // fast pointer distance D = Vt = 2vt = 2d = 2(a+b) = a+b+kc, k >= 1
    // (fast pointer has already run k laps.)
    // so we have: a+b = kc  -->  a = kc-b = (k-1)c + (c-b)
    // c-b is the distance from current meeting point to circle entry
    class Solution {
    public:
        ListNode *detectCycle(ListNode *head) {
            for (ListNode *f = head, *s = head; f; ) {
                if ((f = f->next) && (f= f->next)) {
                    if ((s = s->next) == f) {
                        s = head;
                        while (f != s) {
                            f = f->next;
                            s = s->next;
                        }
                        return s;
                    }
                } else break;
            }
            return NULL;
        }
    };
    

Log in to reply
 

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