Detect Loop in linked list

You are given the head of a singly linked list. Your task is to determine if the linked list contains a loop. A loop exists in a linked list if the next pointer of the last node points to any other node in the list (including itself), rather than being null.

Custom Input format:
A head of a singly linked list and a pos (1-based index) which denotes the position of the node to which the last node points to. If pos = 0, it means the last node points to null, indicating there is no loop.

Examples:

Input: head: 1 -> 3 -> 4, pos = 2
Output: true
Explanation: There exists a loop as last node is connected back to the second node.

Input: head: 1 -> 8 -> 3 -> 4, pos = 0
Output: false
Explanation: There exists no loop in given linked list.

Input: head: 1 -> 2 -> 3 -> 4, pos = 1
Output: true
Explanation: There exists a loop as last node is connected back to the first node.

Constraints:
1 ≤ number of nodes ≤ 10⁴
1 ≤ node->data ≤ 10³       
0 ≤ pos ≤ Number of nodes in Linked List

Approach 01:

class Solution {
public:
    // Function to check if the linked list has a loop.
    bool detectLoop(Node* head) {
        if (head == nullptr || head->next == nullptr) {
            return false;
        }

        Node* slowPointer = head;           // Slow pointer moves one step at a time
        Node* fastPointer = head->next;     // Fast pointer moves two steps at a time

        while (fastPointer != nullptr && fastPointer->next != nullptr) {
            if (slowPointer == fastPointer) {
                return true;  // Loop detected
            }
            slowPointer = slowPointer->next;           // Move slow pointer by one step
            fastPointer = fastPointer->next->next;     // Move fast pointer by two steps
        }

        return false;  // No loop detected
    }
};

class Solution:
    def detectLoop(self, head):
        if head is None or head.next is None:
            return False

        slowPointer = head            # Slow pointer moves one step at a time
        fastPointer = head.next       # Fast pointer moves two steps at a time

        while fastPointer is not None and fastPointer.next is not None:
            if slowPointer == fastPointer:
                return True  # Loop detected
            slowPointer = slowPointer.next           # Move slow pointer by one step
            fastPointer = fastPointer.next.next      # Move fast pointer by two steps

        return False  # No loop detected

Time Complexity:

• Traversal of the Linked List:

  The algorithm uses two pointers: the slow pointer moves one step at a time, and the fast pointer moves two steps at a time. In the worst case, the fast pointer traverses the entire list, which takes \( O(n) \), where \( n \) is the number of nodes in the linked list.

• Overall Time Complexity:

  The total time complexity is \( O(n) \).

Space Complexity:

• Auxiliary Space:

  The algorithm uses two pointers (slowPointer and fastPointer) and no additional data structures, resulting in constant space usage of \( O(1) \).

• Overall Space Complexity:

  The total space complexity is \( O(1) \).