"Linked List Cycle": Detecting Loops with Floyd's Tortoise and Hare Algorithm (Java)

Hello everyone! Today, we're diving into a classic linked list challenge: "Linked List Cycle" (LeetCode #141).

The task is simple: determine if a given linked list contains a cycle. The clever solution for this problem is a testament to pointer manipulation, known as Floyd's Cycle-Finding Algorithm, or more commonly, the "Tortoise and Hare" algorithm.

---

Understanding the Problem:

You are given the head of a singly linked list. A linked list has a cycle in it if there's some node in the list that can be reached again by continuously following the next pointer. Essentially, it means the list loops back on itself at some point.

The problem statement mentions pos as an internal detail (the index of the node where the tail connects). This pos is not passed as a parameter to your function; it's purely for illustrative purposes in the examples to show where the cycle might occur. Your function only receives the head of the list.

Example 1:

• Input: head = [3, 2, 0, -4], pos = 1 (meaning -4 points back to 2)

• Output: true

  • Explanation: The list looks like 3 -> 2 -> 0 -> -4 -> (points back to 2), forming a cycle.

---

My Thought Process & Approach (Floyd's Cycle-Finding Algorithm / Tortoise and Hare):

The naive way to detect a cycle might be to store every visited node in a HashSet and check if we encounter a node already in the set. However, this uses O(N) space, which is not ideal for large lists. The challenge is to do it in O(1) space.

This is where the "Tortoise and Hare" algorithm comes in. Imagine two runners on a track: one is slow (the tortoise), and one is fast (the hare).

• If they are on a straight track, the fast runner will always reach the end first.

• If they are on a circular track, and the fast runner moves faster than the slow runner, they are guaranteed to meet at some point if they start from the same spot (or one starts ahead of the other, as long as they are on the cycle). The faster runner will eventually "lap" the slower one.

Applying this to Linked Lists:

1. Initialize Pointers: We use two pointers, slow (the tortoise) and fast (the hare). Both start at the head of the linked list.

2. Movement:

   • slow moves one step at a time: slow = slow.next;

   • fast moves two steps at a time: fast = fast.next.next;

3. Detection Logic:

   • If there is no cycle: The fast pointer (which moves twice as fast) will eventually reach the end of the list (i.e., become null or fast.next becomes null) before slow ever encounters a loop. In this case, the while loop terminates, and we return false.

   • If there is a cycle: The fast pointer will eventually enter the cycle. Since it's moving faster than slow, and both are traversing the cycle, fast will eventually "catch up to" and meet slow at some node within the cycle. When slow == fast, we know a cycle exists, and we return true.

Why are they guaranteed to meet in a cycle? If they are in a cycle, fast gains one "unit" of distance on slow in each iteration. Imagine the distance between them as d. In the next step, fast moves 2, slow moves 1, so the distance reduces by 1. Since fast is constantly closing the gap, and the track is circular, they must eventually converge at the same node.

---

Java Code Implementation:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast= fast.next.next;
            if(slow == fast){
                return true;
            }
        }
        return false;
    }
}

Time and Space Complexity Analysis:

• Time Complexity: O(N)

  • In the worst case (no cycle, or a cycle very far down the list), the fast pointer traverses the entire list, reaching the end. Since slow moves half as fast, it covers about half the list.

  • If there is a cycle, both pointers eventually enter the cycle. Once slow enters the cycle, fast will meet it within at most one full traversal of the cycle's length (plus some initial traversal to reach the cycle).

  • In both scenarios, the number of steps taken by the pointers is directly proportional to the number of nodes N in the list.

• Space Complexity: O(1)

  • The algorithm uses only a constant number of extra variables (two pointers: slow and fast), regardless of the size of the input linked list.

  • This is the key advantage of Floyd's algorithm over approaches that use a hash set to store visited nodes.