How can you detect a cycle in a linked list? Describe the Floyd’s Cycle-Finding algorithm.?

Detecting a cycle in a linked list is an important problem in computer science. One commonly used algorithm for cycle detection is Floyd’s Cycle-Finding algorithm, also known as the "tortoise and hare" algorithm. The basic idea behind this algorithm is to use two pointers, one moving faster than the other, to traverse the linked list. If there is a cycle in the linked list, then the faster pointer will eventually catch up to the slower pointer and they will meet at a point in the cycle.

Here is an example implementation of Floyd’s Cycle-Finding algorithm in Java:

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}

In this implementation, the hasCycle method takes as input the head node of a linked list and returns true if the linked list contains a cycle, and false otherwise. It initializes two pointers, slow and fast, to the head of the linked list. It then iterates through the linked list, with the slow pointer moving one step at a time and the fast pointer moving two steps at a time. If there is a cycle in the linked list, then the fast pointer will eventually catch up to the slow pointer and they will meet at a point in the cycle. If there is no cycle, then the fast pointer will reach the end of the linked list before the slow pointer catches up to it.

The time complexity of Floyd’s Cycle-Finding algorithm is O(n), where n is the length of the linked list. The space complexity is O(1), as the algorithm only requires two pointers to traverse the linked list.