Find the first node of loop in linked list

Given a head of the singly linked list. If a loop is present in the list then return the first node of the loop else return 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:
 
Output: 3
Explanation: We can see that there exists a loop in the given linked list and the first node of the loop is 3.

Input:
 
Output: -1
Explanation: No loop exists in the above linked list.So the output is -1.

Constraints:
1 <= no. of nodes <= 10⁶
1 <= node->data <= 10⁶ 

Approach 01:

#include <unordered_set>

class Solution {
public:
    Node* findFirstNode(Node* head) {
        unordered_set<Node*> visitedNodes;  // Set to track visited nodes
        
        while (head) {
            if (visitedNodes.find(head) != visitedNodes.end()) {  // If the current node is already visited, return it
                return head;
            }
            visitedNodes.insert(head);  // Mark the current node as visited
            head = head->next;
        }
        
        return nullptr;  // Return nullptr if no cycle is detected
    }
};

class Solution:
    def findFirstNode(self, head):
        visitedNodes = set()  # Set to track visited nodes
        
        while head:
            if head in visitedNodes:  # If the current node is already visited, return it
                return head
            visitedNodes.add(head)  # Mark the current node as visited
            head = head.next
        
        return None  # Return None if no cycle is detected

Time Complexity:

• Traversal:

  The while loop traverses each node in the linked list exactly once, which takes \( O(N) \), where \( N \) is the number of nodes in the list.

• Set Operations:

  For each node, checking if it has been visited takes \( O(1) \) on average, and inserting the node into the set also takes \( O(1) \) on average. Therefore, the time complexity of set operations is \( O(N) \), where \( N \) is the number of nodes in the list.

• Total Time Complexity:

  Since the traversal and set operations together take linear time, the overall time complexity is \( O(N) \).

Space Complexity:

• Auxiliary Space:

  The algorithm uses a set to store the visited nodes, which can contain up to \( O(N) \) nodes in the worst case, where \( N \) is the number of nodes in the linked list.

• Total Space Complexity:

  The total space complexity is \( O(N) \), which accounts for the space used by the set to track the visited nodes.