|
Answer» Example: Input: 1 -> 2 -> 3 -> 4 -> 5 Output: No loop present. Input: 1-> 2 -> 3 -> 4
A |
| V
6 < - 5 Output: Loop present. - Approach 1: Traverse the list one by one, adding node addresses to a Hash Table as you go. If NULL is reached at any time, return false; otherwise, return true if the NEXT of the current nodes points to any of the previously recorded nodes in Hash.
- Solution Code:
// Node structurestruct Node { int data; STRUCT Node* next;};bool findLoop(struct Node* head){ // Hashmap for flagging if a node has been visited unordered_set<Node*> hash_map; while (head != NULL) { // If this node is already present in hashmap it means there is a cycle and so we return true if (hash_map.find(head) != hash_map.end()) return true; // If we are seeing the node for the first time, we insert it in hash map hash_map.insert(head); head = head->next; } // We return false in case there is no loop in the given linked list return false;}Time Complexity: O(n)
Space Complexity: O(n) Here, n is the number of nodes in the given linked list. Explanation: In the above code, the function findLoop detects if a loop is present in a linked list or not. We maintain a hashmap of nodes and as we traverse through the linked list, we flag a node as visited. If we encounter a visited node again, it implies that a loop is present in the linked list and so we return true. - Approach 2: In this approach, we maintain two pointers: slow_pointer and fast_pointer. We initialize both of them with the head of the linked list. We iterate through the linked list until either the fast_pointer becomes NULL or the fast_pointer->next becomes NULL. In each iteration, we update the slow_pointer by moving it one step ahead in the linked list while we update the fast_pointer by moving it two steps ahead in the linked list. If at any POINT, the slow_pointer and the fast_pointer become equal, we return true implying that a cycle is INDEED present in the linked list. This algorithm is also known as Floyd's Cycle finding algorithm.
- Solution Code:
// Node structurestruct Node { int data; struct Node* next;};// RETURNS true if there is a loop in linked list// else returns false.bool findLoop(Node* head){ Node *slow_pointer = head, *fast_pointer = head; while (fast_pointer && fast_pointer->next) { slow_pointer = slow_pointer->next; fast_pointer = fast_pointer->next->next; if (slow_pointer == fast_pointer) { return true; } } return false;} Time Complexity: O(n)
Space Complexity: O(1) Explanation: In the above code, the function findLoop takes in the head of the linked list as an argument and returns true if a loop is present in the linked list else false. We maintain two pointers: slow_pointer and fast_pointer as discussed in the solution approach and keep iterating the linked list until either fast_pointer or fast_pointer->next becomes NULL. At any iteration, if the slow_pointer becomes equal to the fast_pointer, we return true.
|
