Solution to Leetcode 141: Linked List Cycle

In this classic exercise, we need to return if the linked list contains a cycle.

Naive algorithm

The most natural wai of solving the problem is to track all encoutered node in a Set, or a similar data structure, and return false if we encounter an element twice:

public boolean hasCycle(ListNode head) {
    Set<ListNode> set = new HashSet<>();
    while (head != null) {
        if (set.contains(head)) {
            return true;
        }
        set.add(head);
        head = head.next;
    }…