Given the head of a linked list, detect if the given linked list contains a cycle. Return true if there exists a cycle else return false. Below is an example of two linked lists containing cycles.
Approach 1: Using Hashmap.
In this approach, you are going to insert all the nodes one by one inside a hashmap, and whenever you found a condition that a particular node is already present in the hashmap then it means there exists a cycle so return true.
C++ Solution Code:
/*C++ Program detect cycle in a linked list using hashmap*/ #include<bits/stdc++.h> using namespace std; class ListNode{ public: int data; ListNode *next; //constructor ListNode(int data){ this->data = data; this->next = NULL; } }; //creating new node ListNode *newNode(int data){ ListNode *temp = new ListNode(data); temp->next = NULL; return temp; } //function to print linked list void printList(ListNode *head){ ListNode *temp = head; while(temp != NULL){ cout<<temp->data<<" "; temp = temp->next; } } //Function to detect cycle of linked list bool detectCycle(ListNode *head){ unordered_set<ListNode*> hp; //loop to check cycle while(head != NULL){ if(hp.find(head) != hp.end()) return true; hp.insert(head); head = head->next; } return false; } int main(){ ListNode* head = new ListNode(1); head->next = new ListNode(2); head->next->next = new ListNode(3); head->next->next->next = new ListNode(4); head->next->next->next = head; //cycle formation bool check = detectCycle(head); if(check) cout<<"Linked List contains a cycle."; else cout<<"Linked List does not contain a cycle."; return 0; }
Linked List contains a cycle.
- Time Complexity: O(n) where n is the number of nodes present.
- Space Complexity: O(n) because we are using one extra hashmap.
Approach 2: Two Pointer Approach (Slow and Fast Pointer).
In this approach, you need to use two pointers and one pointer will move slower than the other pointer. If the linked list contains a cycle then slow and fast pointers must meet at some point and if they meet each other at any point it means there exists a cycle.
- Initialize two pointers, slow and fast with the head of the linked list.
- Traverse the list, every time the slow pointer moves one step, and the faster moves two steps
- If there is a cycle then both slow and fast pointers will meet at some point, return true if they meet else return false.
C++ Solution Code:
/*C++ Program detect cycle in a linked list using two pointer approach*/ #include<bits/stdc++.h> using namespace std; class ListNode{ public: int data; ListNode *next; //constructor ListNode(int data){ this->data = data; this->next = NULL; } }; //creating new node ListNode *newNode(int data){ ListNode *temp = new ListNode(data); temp->next = NULL; return temp; } //function to print linked list void printList(ListNode *head){ ListNode *temp = head; while(temp != NULL){ cout<<temp->data<<" "; temp = temp->next; } } //Function to detect cycle of linked list bool detectCycle(ListNode *head){ if(head == NULL) return false; ListNode* slow = head; ListNode* fast = head; while(fast != NULL && fast->next != NULL){ slow = slow->next; fast = fast->next->next; if(slow == fast) return true; //cycle detected } return false; } int main(){ ListNode* head = new ListNode(1); head->next = new ListNode(2); head->next->next = new ListNode(3); head->next->next->next = new ListNode(4); head->next->next->next = head; //cycle formation bool check = detectCycle(head); if(check) cout<<"Linked List contains a cycle."; else cout<<"Linked List does not contain a cycle."; return 0; }
Linked List contains a cycle.
- Time Complexity: O(n) where n is the number of nodes in the linked list.
- Space Complexity: O(1)
Related Articles:
No comments:
Post a Comment