Problem: Our task is to determine is there any loop/cycle in a Linked List or not?
Required Knowledge: Singly Linked List | Data Structure
Explanation:
image source: hackerrank.com
There is a "slow" pointer that moves one node at a time. There is a "fast" pointer that moves twice as fast, two nodes at a time.
A visualization as slow and fast pointers move through the linked list with 10 nodes:
1: |sf--------|
2: |-s-f------|
3: |--s--f----|
4: |---s---f--|
5: |----s----f|
At this point one of two things is true:
1) the linked list does not loop (checked with fast != null && fast.next != null && slow!=null) or
2) it does loop. Let's continue visualization assuming it does loop:
6: |-f----s---|
7: |---f---s--|
8: |-----f--s-|
9: |-------f-s|
10: s == f
If the linked list is not looped, the fast pointer finishes the race at O(n/2) time; we can remove the constant and call it O(n). If the linked list does loop, the slow pointer moves through the whole linked list and eventually equals the faster pointer at O(n) time.
CODE in C++:
#include<bits/stdc++.h>
using namespace std;
/*1. Single Linked List Structure*/
typedef struct Node{
int data;
Node* next;
}Node;
/*Creates a Linked List with the given size*/
Node* Create_SingleLL(int n){
int data;
Node *head=nullptr,*tail=nullptr;
while(n--){
cin>>data;
if(!head){
head = (Node*)malloc(sizeof(Node));
head->data = data;
head->next = nullptr;
tail = head;
continue;
}
Node* t = (Node*) malloc(sizeof(Node));
t->data = data;
t->next = nullptr;
tail->next = t;
tail = t;
}
//creates a cycle
tail->next = head;
return head;
}
/**
* @brief dertermines is there any loop/cycle in the linked list
* To Understand this you can assume a variable slow as tortoise and fast as a hare.
* If there exists a cycle in the linked list, before reaching the slow of the last node of the list
* the fast will will meet the slow, otehrwise not.
*
* @param head
* @return true
* @return false
*/
bool IsCycle(Node* head){
if(!head) return false;
Node* slow = head, *fast=head;
while(slow && fast && fast->next ){
slow = slow->next;
fast = fast->next->next;
if(slow==fast) return true;
}
return false;
}
int main(){
int n;
cout<<"Enter the length of the Linked List: ";
cin>>n;
Node* head = Create_SingleLL(n);//creates a cycle,
//the last node is connected
//with the first node.
if(IsCycle(head)) cout<<"Cycle Exists!\n";
else cout<<"There is no Cycle in the linked list!\n";
free(head);
return 0;
}
Posts
No comments