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

This is pretty classical and well-know problem about linked list. One way is just to put all linked list to for example hash table and check if we have repeating elements. However it will take O(n) space. There is better solution with only O(1) complexity. Imagine the following example: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 3, the list with loop. Idea is to use two pointers, one is slow and one is fast, let us do several steps:

  1. At the beginning, both of them at number 1.
  2. Next step, slow pointer at 2 and fast at 3.
  3. Next step, slow pointer at 3 and fast at 5.
  4. Next step, slow pointer at 4 and fast at 3.
  5. Next step, slow pointer at 5 and fast is also 5, so we have the same element and we return True.

If we do not have loop we will never have equal elements, if we have loop, because slow pointer moves with speed 1 and fast with speed 2, fast pointer will always gain slow one.

Complexity: time complexity is O(n), space complexity is O(1).

class Solution:
    def hasCycle(self, head):
        slow = fast = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if slow == fast: return True
            
        return False

Similar problems: 142: Linked List Cycle II: 287. Find the Duplicate Number:

If you like the solution, you can upvote it on leetcode discussion section: Problem 0141