How to Determine if a Linked List Has a Cycle

Problem Description
Given the head node of a linked list, determine whether a cycle exists in the list. A cycle in a linked list is defined as: a node's next pointer points to a previously visited node in the list, forming a cyclic structure. Implement a function that takes the head node of the linked list as input and returns a boolean value (true if a cycle exists, false otherwise).

Solution Approach
The classic method for detecting a cycle in a linked list is to use the Fast and Slow Pointers (Floyd Cycle Detection Algorithm). The core idea is:

1. Set two pointers, a slow pointer that moves one step at a time and a fast pointer that moves two steps at a time.
2. If a cycle exists in the linked list, the fast pointer will eventually catch up to the slow pointer (they meet).
3. If there is no cycle, the fast pointer will reach the end of the list (encounter null) first.

Detailed Steps

1. Initialize Pointers

   • Define two pointers slow and fast, both initially pointing to the head node.
   • Handle the case of an empty list (head is null).

2. Traverse the List

   • Use a loop with the condition fast != null && fast.next != null (ensuring the fast pointer can safely move two steps).
   • The slow pointer moves one step each time: slow = slow.next.
   • The fast pointer moves two steps each time: fast = fast.next.next.

3. Detect Meeting

   • After each move, check if slow == fast:
     • If equal, it means the fast and slow pointers have met, indicating a cycle exists. Return true.
     • If the fast pointer reaches the end of the list (fast is null or fast.next is null), it means there is no cycle. Return false.

4. Mathematical Principle

   • Assume the length outside the cycle is a, and the length inside the cycle is b.
   • When the slow pointer enters the cycle, the fast pointer is already inside the cycle, and the relative speed of the fast pointer to the slow pointer is 1 step per move.
   • Since the cycle length is finite, the fast pointer will catch up to the slow pointer in at most b steps.

Example Code (Java)

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        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;
    }
}

Complexity Analysis

• Time Complexity O(n):
  • When there is no cycle, the fast pointer reaches the end first, with approximately n/2 traversals.
  • When there is a cycle, in the worst case, after the slow pointer traverses the outside distance a, the fast pointer needs to chase b steps (a+b=n), still O(n).
• Space Complexity O(1): Only two pointers are used.

Extended Problem
If it is required to find the entry node of the cycle, after the fast and slow pointers meet, reset the slow pointer to the head node. Then move both pointers one step at a time. The node where they meet again is the entry point of the cycle (mathematically provable).