How can the presence of collisions be determined using a linked list?

To detect the presence of cycles (loops) in a linked list, the Floyd’s Cycle-Finding Algorithm is often used. The idea is to use two pointers:

• A slow pointer (turtle) moves one element at a time.
• A fast pointer (hare) moves two elements at a time.

If there is a cycle in the list, the fast pointer will eventually catch up to the slow pointer, and they will point to the same node. If there is no cycle, the fast pointer will reach the end of the list (null).

Example in Java:

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; // cycle detected
        }
    }
    return false; // no cycle
}

This method is efficient and does not require additional memory.