LeetCode 141 - Linked List Cycle

Given a linked list, determine if it has a cycle in it.
  Use fast and low pointer. The advantage about fast/slow pointers is that when a circle is located, the fast one will catch the slow one for sure.

https://leetcode.com/articles/linked-list-cycle/

• 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. $\text{Number of iterations} = \text{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 $\dfrac{\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 "$\text{cyclic length K}$" and the speed difference is 1, we conclude that
       $\text{Number of iterations} = \text{almost}$ "$\text{cyclic length K}$".
  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)$.

  public boolean hasCycle(ListNode head) {

    if (head == null || head.next == null) {

      return false;

    }

    ListNode slow = head;

    ListNode fast = head.next;

    while (slow != fast) {

      if (fast == null || fast.next == null) {

        return false;

      }

      slow = slow.next;

      fast = fast.next.next;

    }

    return true;

  }

    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
 
        if(head == null)
            return false;
 
        if(head.next == null)
            return false;
 
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
 
            if(slow == fast)
                return true;
        }
 
        return false;
    }

  public boolean hasCycle(ListNode head) {

    Set<ListNode> nodesSeen = new HashSet<>();

    while (head != null) {

      if (nodesSeen.contains(head)) {

        return true;

      } else {

        nodesSeen.add(head);

      }

      head = head.next;

    }

    return false;

  }

Read full article from Leetcode – Linked List Cycle