Intuition

Do a hash on the value itself, but this has a flaw that different nodes can have the same value, therefore not forming a cycle.

A optiomal approach is to use the slow-fast approach.

One pointer jumping one node at a time, the other jumping two. If the faster points reaches the end (node.next == null), then we don’t have a cycle. When both slow and fast meets each other, we found our cycle.

Approach

Use two pointers, one always jumping to the next, the other always jumpting to the next-next.

At any iteration if the fast pointer is null, or it’s next is null, then we don’t have a cycle. At any iteration, if slow == fast, the we found our cycle and we can stop.

This is the optimal solution because it memory efficient. The other approach would be to store a set of seen nodes, but this requires O(n)

Complexity

• Time complexity: O(n)

• Space complexity: O(1)

Code

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head is None:
            return False
        slow = head
        fast = head.next
        while slow!=fast:
            if fast is None or fast.next is None:
                return False
            slow = slow.next
            fast = fast.next.next
        return True