Detecting Cycles in a Singly Linked List

In this task, our goal is to determine if there’s a loop in a given linked list. Imagine you’re navigating through a series of interconnected rooms. The question is whether you can keep moving from one room to another and eventually return to a room you’ve visited before. Our task is to detect if such a loop exists in the linked list. We can utilize smart algorithms to efficiently solve this problem without the need for cheesecake-related analogies.

class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
 }

public boolean hasCycle(ListNode head) {
    // Initialize two pointers, slow and fast, both starting at the head of the list
    ListNode slow = head; // Slow pointer moves one node at a time
    ListNode fast = head; // Fast pointer moves two nodes at a time
    
    // Traverse the list until either fast pointer reaches the end or encounters a null pointer
    while (fast != null && fast.next != null) {
        // Move slow pointer one step forward
        slow = slow.next;
        // Move fast pointer two steps forward
        fast = fast.next.next;
        
        // If slow and fast pointers meet at the same node, a cycle is detected
        if (slow == fast) {
            return true;
        }
    }
    
    // If fast pointer reaches the end of the list, there is no cycle
    return false;
}

Explanation:

• We start with two pointers, slow and fast, both initially pointing to the head of the linked list.
• In each iteration of the while loop, the slow pointer moves one step forward while the fast pointer moves two steps forward.
• If there’s a cycle in the linked list, the fast pointer will eventually catch up with the slow pointer.
• If there’s no cycle, the fast pointer will reach the end of the list.
• This algorithm is efficient because it traverses the linked list in a single pass, with time complexity O(n), where n is the number of nodes in the list.

Happy codding…!!!