链表环判断

Jun 02, 2020
bool IsLoop(Node* node) {
    node = node->next;
    Node* fast = node;
    Node* slow = node;
    while(fast) {
        fast = fast->next;
        if (!fast) return false;
        fast = fast->next;
        if (!fast) return false;

        // fast 成功走了两步
        if (fast == slow) return true;

        slow = slow->next;
    }
}

快慢指针 fast走两步 slow走一步

由于 slow 走完一圈的时候 fast可以走两圈 所以会收敛

Great! You've successfully subscribed.
Great! Next, complete checkout for full access.
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.