https://leetcode.com/problems/linked-list-cycle/description/?envType=study-plan-v2&envId=top-interview-150

Floyd's Cycle Finding Algorithm

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr){
            return false;
        }
        ListNode* slow = head;
        ListNode* fast = head->next;
        while(slow != fast){
            if (fast == nullptr || fast ->next == nullptr){
                return false;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        return true;
    }
};

Complexity analysis

• Time complexity : $O(n)$.

  Let us denote $n$ as the total number of nodes in the linked list. To analyze its time complexity, we consider the following two cases separately.

  • List has no cycle:

    The fast pointer reaches the end first and the run time depends on the list's length, which is $O(n)$.

  • List has a cycle:

    We break down the movement of the slow pointer into two steps, the non-cyclic part and the cyclic part:

    1. The slow pointer takes "non-cyclic length" steps to enter the cycle. At this point, the fast pointer has already reached the cycle. Number of iterations=non-cyclic length=$N$
    2. Both pointers are now in the cycle. Consider two runners running in a cycle - the fast runner moves 2 steps while the slow runner moves 1 steps at a time. Since the speed difference is 1, it takes $\frac{\text{distance between the 2 runners​}}{\text{difference of speed}}$loops for the fast runner to catch up with the slow runner. As the distance is at most cyclic length $K - 1$ and the speed difference is 1, we conclude that $\text{Number of iterations=at most cyclic length } K - 1$.

  Therefore, the worst case time complexity is $O(N+K)$, which is $O(n)$.

• Space complexity : $O(1)$.

  We only use two nodes (slow and fast) so the space complexity is $O(1)$.