Brent's Cycle Detection Algorithm


  • 0
    H
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    // Brent's Algorithm.
    class Solution {
    public:
        ListNode *detectCycle(ListNode *head) {
            // corner condition.
            if (head == nullptr) {
                return nullptr;
            }
            
            ListNode *tortoise = head;
            ListNode *hare = head->next;
            // 2^0
            int next_boundary = 1;
            int lam = 1;
            while (hare != nullptr && hare != tortoise) {
                // boundary test?
                if (lam == next_boundary) {
                    // move to next boundary.
                    next_boundary *= 2;
                    lam = 0;
                    tortoise = hare;
                }
                hare = hare->next;
                ++lam;
            }
            
            if (hare == nullptr) {
                return nullptr;
            }
    
            tortoise = hare = head;
            while (lam > 0) {
                hare = hare->next;
                --lam;
            }
            while (hare != tortoise) {
                hare = hare->next;
                tortoise = tortoise->next;
            }
            return tortoise;
        }
    };

Log in to reply
 

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