Cycle Detection
byharsha_sclacrone The old "tortoise and the hare" problem. Essentially, the "fast" pointer moves 2x the speed as the "slow" pointer. If there is a cycle, they will meet.
int HasCycle(Node head) { if (head == null){ return 0; } Node slow = head; Node fast = head; while (fast != null && fast.next != null){ slow = slow.next; fast = fast.next.next; if (slow == fast){ return 1; } } return 0; }Tofurkey Great solution and explanation!
byronrpv_rckr can't get the explanation, do not catch the analogy, there is no such tale in my country i guess, ja ja plz can someone explain me the code a little bit?? thanks men
corey_t_ferguson The tale isn't important.
There is a "slow" pointer which moves one node at a time. There is a "fast" pointer which moves twice as fast, two nodes at a time.
A visualization as slow and fast pointers move through 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 are true: 1) the linked list does not loop (checked with
fast != null && fast.next != 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.
Mr_BrainTurner nice one
jens_vanderhaeg1 What would you say the time complexity is? O(N)?
Abushawish Yes, O(N) because you have to go through every element regardless of factor.
hammeramr would this be O(1) // because we know the max size is 100 and O(100) = O(k) = O(1)
boolean hasCycle(Node head) { if(head == null || head.next == null) return false; Node n = head; // list max size = 100 so after 100 steps if n != null return true for(int i = 0; i < 100; i++) { if(n == null) { return false; } else { n = n.next; } } return true; }
ekuznets [deleted]
khandelwalnites1 [deleted]Madhav_Bhatt No, it will still be O(n), that's the definition of big-O notation. Simply think like below. k values(i/p size) loop rotation 1 1 100 100 n n
Hence order is n. We should not take input size constant while calculating time complexity.
usmanajmal Yes, this should be O(1). She didn't take it constant. The given question has provided a constant max size of 100 for the linked list.
ashu_msr19 n is a variable used in big O notation for unknown test cases. if n=1, O(1). if n=100, O(100). if n=?, O(n).
unwrittenwater4 [deleted]ashu_msr19 wow! man ur comment was incredibly stupid ,its good that at least u can code.
maitrey2112 Wow!. Man your grammar is incredibly stupid and incorrect , it's good you can at least code.
dharmikp572 I did similar thing in java XD
jasmeet17 Can some body explain why there are 10 downvotes?
abhinavkushagra Not necessarily. It mayn't find the cycle in first go. So, we can't say it's of O(n).
nike3801 Nice explanation.
askarovdaulet Great except the first three lines of the function are redundant. You will still fall through to return 0, because in case head is null, fast = null and you skip the while loop altogether.
hekuang But what if the last pointer points back to the first one?
askarovdaulet [deleted]askarovdaulet Will still work. Imagine there are only two elements [head,tail] and tail.next points to head. Then on the second iteration of while loop, slow==fast==head and you return 1. You can show that in general you will detect the loop of tail back to head on the n-th iteration of the while loop where n is the total number of elements.
hekuang Right! Thanks for the explanation.
ethan_sec In this case, I feel this is an overkill. There's a constraint that the list is <=100 nodes. So, why traverse the list several times by definition until they meet.
I solved it (in Python) with a counter:
def has_cycle(head): count = 0 while head and count<101: count += 1 head = head.next return count>100
rouzbeh_asghari1 Thanks for your solution. How about this solution. I tried to make it more general. What if we don't know about 100?
visited = [] def has_cycle(head): if head: visited.append(head.data) if head.next: if head.next.data in visited: return True else: has_cycle(head.next) else: return False else: return False
shubhampachori6 What if two nodes in a list have the same data in two nodes but they are not in a cycle?
ishabandi Then store the node address? My solution works on the test cases. Have a look?
def has_cycle(head): if head is None: return False visited = [] node = head flag = 99 while node is not None: if node not in visited: visited.append(node) else: flag = 1 return True node = node.next if flag==99: return False
Worst case here will be O(n^2) right?
adityaloshali1 [deleted]adityaloshali1 this works perfectly
def has_cycle(head): x = [] while head: if head in x: return True else: x.append(head) head=head.next return False
ishabandi Yes! yours is cleaner. too many redundant lines in mine. What about the complexity? Will it work under huge lists?
adityaloshali1 Yes it will work for huge lists too . Either this algorithm , or use the Rabbit and Hare algorithm (fast and slow pointer) . that can reduce the time for travelling the list . but either way it's a brute force algorithm . you'll have to travel till the end of list to identify the presence of a cycle
thebopshoobop You should use a set rather than a list. If you check the wiki, you'll see that
x in s
operations on lists are O(n) on lists but average O(1) on sets, while adding to both is O(1). Therefore, as written this algorithm is O(n^2), but would be O(n) with a set.
jcflorezr [deleted]
ojhasaurabh2099 [deleted]
gregigusa [deleted]
vshantam Yes ,Your Solution is much more general and understandable but you used too much conditionals here is my approch
def has_cycle(head): temp=head;visited=[] while temp.next!=None: if temp.data in visited: return True else: visited.append(temp.data);temp=temp.next return False
maitrey2112 If you don't care about the list after the program(like here) , you can reduce worst case complexity to O(N) and in other case O(k), where k is no. of nodes you have visited , it'll be better than O(100) and O(n^2).
def has_cycle(head): x = head y = head while x: if (x.next=="visited"): return True else: y = x.next x.next="visited" x=y return False
henryjw visited = set()It's probably a good idea to use sets instead of arrays for lookups since the difference is
O(n)vsO(1)lookup time. It doesn't matter for the size in this problem, but it'll make a difference in problems with larger input sizes.
DishaParwani [deleted]NorthernLight The 'slow' pointer never traverses the list more than once if you solve using the 'tortoise and hare' method. The worst case (entire list is traversed once) occurs when the cycle starts at the header node.
You see, since the number of nodes between the 'slow' and the 'fast' pointer decreases by 1 every iteration (in a cycle), once the 'slow' pointer reaches the first node of the cycle, it has to traverse only as many more nodes as the number between the two pointers before they meet(Remember, the number is counted starting from the 'fast' node, and in the direction it's travelling (clockwise/anticlockwise)).
dougbeck I had a similar solution, except recursive and js. Not sure if there is a bug in this code or the solution checker:
var count = 0; var max = 100; function hasCycle(head) { if (head === null) { return false; } if (count > max) { return true; } count++; return hasCycle(head.next); }
edit: I guess there is a problem with state. Removing the recurrsion and encapsulating the counter passes
¯\_(ツ)_/¯HHWWHH Another way in python:
def has_cycle(head): cur=head while cur!=None: pointer=cur while pointer!=None: if pointer.next!=cur: pointer=pointer.next else: return 1 cur=cur.next return 0
positivedeist_07 I did exactly as per ur logic but I get compilation errors. The output is not the expected one. It shows segmentation fault :(
and, should we not make use of the fact that the list is restricted to size 100?
pls help me out!!
alpha52omega41 Also known as Flyod Cycle finding algorithm..
ishabandi I hope my understanding is correct.
You are just checking if any of the 'next' are same by using to iterables?
benraw11 [deleted]mjhere Good solution. Thank you:)
chanchanman Yes! The Floyd Algorithm! :D
elaines Why it's related to this algo? :) I checked floyd, but didn't get any clue of their similarity. could you explain a bit?
MoulikGupta The old "tortoise and the hare" problem in python.
MoulikGupta The old "tortoise and the hare" problem in python.
def has_cycle(head): cycle=False slow=head fast=head while head and head.next: if slow==fast: cycle=True break slow=slow.next fast=fast.next.next return cycle
naitik0212 If there are just two nodes in the linked list with a cycle, how will it work?
yash324 slow will increment by 1 and fast will increment by 2, they will be the same every alternate loop.
abhinavmane113 Impressive solution. Btw Add null check for fast pointer after if statement in while loop, in some cases segmentaion fault occurs.
rollins_jackson Is this classic CS material or something?
prempaljee111 bro im confused of if condition bcoz when fast is updated loop will again begins then when will if condition be checked . plz guide me
zzmmss Easy stroy and deep Zen. Incredible!
ShubhamK271999 See this one has O(1) complexity
bool has_cycle(Node* head) { if(head==NULL||head->next==NULL) return head; int index=0; Node* temp= head; while(temp && index<101){ index++; temp=temp->next; } if(index==101) return 1; return 0; }
abhinavkushagra (-__-) Seriously? You're kidding us? You lose your O(1) the time you used while loop.
ShubhamK271999 Boy! The order is independent of the size. It does not matters whether you use N=2/3/6...100. Every time its gonna take the same time bro! A consant time is always of O(1). Isn't it?
abhinavkushagra No! Time is constant, yes. But size is'nt. The code that you've created by no means, will give you constant time for different sizes. I mean, your time complexity depends on the size.
ShubhamK271999 Okay! If there will be a loop, it will continue till the index reaches 101 from 0 but if no loop is there it will depend on the size. So its of order O(1) for looped one and O(n) for non looped. Now am I correct?
abhinavkushagra Not exactly! :\
kharcheavinash11 [deleted]andy17 Hi, why it isn't working with the code
while(slow!=NULL && slow.next!=NULL) In both sense I think it should work,pls help me out.
dimahwang1 Thank you for great solution, however why is it the case that in C++ fast hast to point to head's next as opposed to both slow and fast pointing to head in Java. Thanks.
bool has_cycle(Node* head) { // Complete this function // Do not write the main method if(head == NULL) return false; Node* slow = head; Node* fast = head->next; while(fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; if(fast == slow) return true; } return false; }
gan_mit08 [deleted]
hshah8831 Can someone please explain the input 1, and the output 01101. I understand that there are 5 linked list given as input, and each input integer in output says whether the corresponding lined ist has cycle or not. I am getting output 01111. can any of the moderator give the 4th input linked list. It would be helpful in debugging.
littleninja Edit: The problem was (of course) in my logic. I had two references in the list, but they needed to start at different points so that they didn't fail the first check.
My check compares Node.data and I suspect there may be a non-unique value in the list. All I see for input for Testcase 0 and Testcase 1 is "1". I'm using the Java language option. Frustrating.
sothy_chan Not sure what's up with the testcase either, but the reason why it's not passing is because it says "revisiting a node." A node consists more than just the node.data. Two different nodes can have the same data. So to check node.data is the wrong logic.
littleninja Correct, but that's a red herring. My first attempt did a Node==Node check and this is what I returned to. I tried Node.data==Node.data as I was troubleshooting, but this isn't a good way to test (since it fails if the linked list has duplicate data values). The problem with my implementation was where I started the two node references. I initialized both at head, did my checks, then incremented at different speeds. Obviously if they start at the same position and I check to see if the nodes are the same, they're going to fail. The way I fixed it was by initializing one node at head and the other at head.next. Solved.
ak47gyani I dint understand. If you start both pointers at head and increment them at different speeds, then why ll it fail?
mohitaggarwal516 it will fail in the first case only. It wont go further.
krishzinx cant we first increament the pointers and then check??
varad2512 The simpler way just change the way you compare.Instead of node->data compare the node's addresses.Works!
nijwm21 ur same logic applied but i am getting runtime error in testcase 0.can u please tell me whats the wrong with my code ?
pnanda Yes you are correct. I just wasted 20 minutes trying to debug this issue. In my case i had a slow pointer and a fast pointer (running at 2x speed of slow pointer). Thanks !
VikashYadav You don't need to compare data as in a cyclic loop all entries may be different(explained in 2nd test case). My code iff you want to check- Node current=head; for(int i=0;i<100;i++){
if(current==null){ return 0; } current=current.next; } return 1;virajh If the code above is your solution, it is very incorrect since the assumption is nodes will not be greater than 100.
t_egginton no, it says 0 <= listSize <= 100. Now, unless their variable names are chosen terribly you could assume that this means there is never more than 100 nodes in the list. therefore if you iterate through 100 times and don't hit a NULL node then you know it must be a cycle
Gorakh_Nigam what if cycling has been done twice??
manni_reies LOL, I came up with the same solution, it's a cheat solution thought lol :P
Yeetesh haha i came to the same solution but it felt really noob to use it :P
positivedeist_07 Can u pls explain what u did here corresponds to the question asked?
RaoPisay Well I did it in java using hashCode()
ja5hga1a Was this issue resolved or the solution ever found??? I am facing the same issue. Exactly the same output as yours.
sothy_chan My solution was to store the node in an array list, the node, not just node.data. Then check to see if the list already contains the node.
agodfrey3 if instead of an array list, you use a hash set, you can reduce the complexity down to O(n) because lookup in a hash set is a constant time operation instead of logarithmic or linear in your array ( depending if your array is sorted or not) .
littleninja Depends on how you're trying to solve, but I figured out what was wrong with my implementation. I posted my fix in another comment: https://www.hackerrank.com/challenges/detect-whether-a-linked-list-contains-a-cycle/forum/comments/63711
VikashYadav The output is final output after testing all sample cases but the input shown are the inputs till which your program continues be executing without giving any runtime error.And most probably your program is giving null pointer exception in first test case itself therefore it is not showing further inputs to be tested.
Bonniesaur [deleted]
singh_mona I also got the same output. And I am not able to undrstand the input. My code:
bool has_cycle(Node* head) { if(head==NULL) return false; if(head->next=head) return true; Node *slow=head; Node *fast=head->next; while(slow&&slow->next) { if(slow==fast) return true; slow=slow->next; fast=fast->next->next; } return false; // Complete this function // Do not write the main method }
How to olve this issue?
edward_ribeiro hey,
if(head->next=head)is not mean to be
if(head->next==head)you are using
assignmentinstead ofequality.Also, your while loop is evaluating
slowandslow->nextthat are pointers to memory address, they are!= 0(that is, true). I guess you meanwhile (slow != NULL && slow->next != NULL), right? Finally,fastreaches the end of the list before slow (if it does not contains cycles), so you should check forfastin the while expression, don't you?Cheers!
rishindrareddy [deleted]
Piyushpky there are two cases where the loop breaks 1st one is when fast pointer reaches to NULL(which means while(fast->next!=NULL) ) and 2nd is when slow==fast. check these condition. if(fast->next==NULL) return false; else true;
sgoel01 I took two pointers from head. Increased one pointer by 2 with every iteration and another pointer with 1. If there is loop they will somehow meet in the loop and will return 1. If any of them encounters NULL return 0 :)
sidthekidder Wow, that's something unique
kr_abhinav What you are talking about is floyd-cycle finding algo. If you found it yourself,commendable!
krishnkant_ i've got another way: run a counter variable (k) to count the no. of nodes we have transversed in the linked list and if any node in the linked list points NULL (while k<100) then the list surely does not contain any cycle.
i_rnb @krishnkant_ Sure that's a way, but that's cheat. In practical situation, you never know the maximum length of the linked list. Floyd's cycle detection algo is the most elegant solution.
hugo_ratiney Smart !
gowthamprakaash1 true logic is correct not a cheat if it contains cycle,then it will cycle cycle cycle....
nripesh21 elegant!
ujjwalsaxena Thanx!! did the same and Voilaa..
boolean hasCycle(Node head) { Node n=head; Node n1=head; boolean present=false; while(n!=null && n.next!=null) { n=n.next.next; n1=n1.next; if(n==n1) { present=true; break; } } return present; }
WeilanYang Well, I didn't know the floyd algo... I could only think of using a Hashset. I don't know if it's allowed to import java.utils, but things becomes insanely easy if you switch to python.
def HasCycle(head): nodes = set() while (head != None): if (head in nodes): return 1 nodes.add(head) head = head.next return 0arunkumar_123 In my first approach, I was trying to use a hash table to to keep track of all the nodes visited till now. As soon as we get a node which is already present in hash table.. we can say that linked list contains a cycle. However, this approach is relately complex and requires some extra space. Fast and slow pointer method of finding loop in a linked list data structure is better.
hugo_ratiney I did the same, came here to see if there was a better way... was not disappointed !
Abushawish Did it using HashSet in Java, no problem.
boolean hasCycle(Node head) { if (head == null) return false; Node hare = head; HashSet<Node> nodesVisited = new HashSet<Node>(); while (hare != null) { if (nodesVisited.contains(hare)) return true; nodesVisited.add(hare); hare = hare.next; } return false; }
m_balajee [deleted]
saif01md do the last statement always return false ?? what is the meaningof return false in the last line.I think it should always print false as it is hard coded in the last line.
festmeny Inside the while loop if there's a node that has been visited before, we return true as the list contains a cylce:
if (nodesVisited.contains(hare)) return true;
If hare beceomes null in one point, it means that the list has been fully visited (there's no cylce in it), so the while loop brakes. The last line runs only if the while broke, which happens only if there's no cycle in the list.
m_balajee [deleted]m_balajee [deleted]m_balajee What if the node points to itself?
Abushawish [deleted]
DanHaggard [deleted]
manikhanuja1981 boolean hasCycle(Node head) { if(head == null){ return false; } Node fast = head; while(head.next != null && fast != null){ head = head.next; fast = fast.next.next; if(head == fast){ return true; } } return false; }
nasser85 If the
headcan be converted to JSON without an error being thrown, there are no cycles.function hasCycle(head) { try { JSON.stringify(head) return 0; } catch(err) { return 1; } }
kaivanshah1663 I Guess this will be the simplest in python....
def has_cycle(head): if head.next == None: return 0 else: return 1
nandkarthik Important: I was checking only the values. But, it seems like we should check by reference not by data value.
Parthasch Using Floyd Cycle alogrithm O(n)
oolean hasCycle(Node head) {
Node slowPtr=head; Node fastPtr=head; while(fastPtr!=null && fastPtr.next!=null) { fastPtr=fastPtr.next.next; slowPtr=slowPtr.next; if(slowPtr==fastPtr) return true; } return false;}
2010prashant In Java..
boolean hasCycle(Node head) { if(head==null || head.next==null) { return false; }
Node pointer1=head; Node pointer2=head;
while(pointer2!=null && pointer1!=null) { if(pointer1==pointer2.next) { return true;
} pointer1 = pointer1.next; pointer2 = pointer2.next.next;
}
return false;
}
anshuman_rohella Simple C++ solution.
bool has_cycle(Node* head) { Node *slow = head;//slow pointer Node *fast = head;//fast pointer bool cycle = false; while(fast != NULL) { slow = slow->next; // goes slower fast = fast->next; // goes faster fast = fast->next; if(slow == fast) // if they meet => cycle.. easy { cycle = true; break; } } return cycle; // Complete this function // Do not write the main method }
yilmazneo If the list has only one element, then doesn't that break your code? The reason is your second fast = fast->next would be on NULL->next.
anshuman_rohella Thanks for the comment. Yes, I forgot to add a corner case :P
Sort 358 Discussions, By:
Please Login in order to post a comment