Remove loop in Linked List

Given the head of a linked list that may contain a loop.  A loop means that the last node of the linked list is connected back to a node in the same list. The task is to remove the loop from the linked list (if it exists).

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.

The generated output will be true if there is no loop in list and other nodes in the list remain unchanged, otherwise, false.

Examples:

Input: head = 1 -> 3 -> 4, pos = 2
Output: true
Explanation: The linked list looks like

A loop is present in the list, and it is removed.

Input: head = 1 -> 8 -> 3 -> 4, pos = 0
Output: true
Explanation: 

The Linked list does not contains any loop. 

Input: head = 1 -> 2 -> 3 -> 4, pos = 1
Output: true
Explanation: The linked list looks like 

A loop is present in the list, and it is removed.

Constraints:
1 ≤ size of linked list ≤ 10⁵

Approach 01:

#include <unordered_set>
using namespace std;

class Solution {
public:
    // Function to remove a loop in the linked list.
    void removeLoop(Node* head) {
        unordered_set<Node*> visitedNodes;  // Set to store visited nodes
        Node* currentNode = head;  // Pointer to traverse the list
        Node* previousNode = nullptr;  // Pointer to track the previous node

        while (currentNode) {
            if (visitedNodes.find(currentNode) != visitedNodes.end()) {  // If a loop is detected
                previousNode->next = nullptr;  // Break the loop
                return;
            } else {
                visitedNodes.insert(currentNode);  // Mark the current node as visited
                previousNode = currentNode;  // Update previous node
                currentNode = currentNode->next;  // Move to the next node
            }
        }
    }
};

class Solution:
    # Function to remove a loop in the linked list.
    def removeLoop(self, head):
        visitedNodes = set()  # Set to store visited nodes
        currentNode = head  # Pointer to traverse the list
        previousNode = None  # Pointer to track the previous node
        
        while currentNode:
            if currentNode in visitedNodes:  # If a loop is detected
                previousNode.next = None  # Break the loop
                return
            else:
                visitedNodes.add(currentNode)  # Mark the current node as visited
                previousNode = currentNode  # Update previous node
                currentNode = currentNode.next  # Move to the next node

Time Complexity:

• Traversal:

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

• Set Operations:

  For each node, checking if it is visited takes \( O(1) \) on average, and inserting a node into the set also takes \( O(1) \) on average. Thus, the time complexity for all set operations is \( O(N) \).

• Total Time Complexity:

  The overall time complexity is \( O(N) \) as traversal and set operations are linear in terms of the number of nodes.

Space Complexity:

• Auxiliary Space:

  A set is used to store visited nodes. In the worst case, the set may store up to \( O(N) \) nodes, where \( N \) is the number of nodes in the linked list.

• Total Space Complexity:

  The total space complexity is \( O(N) \) due to the space required by the set.