clacrone 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.
RA1511003010655 Sorry this might seem silly but as soon as fast reaches the last node it will exit right? I mean this is a singly linked list so for fast to reach back to slow, how is that possible? (if there is a cycle that is)
amritgg977 its called Floyd’s Cycle detection algorithm. you can search for it for better explanation.You can watch videos also at https://www.youtube.com/results?searchquery=Floyd%E2%80%99s+Cycle+detection+algorithm
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
abhinavkushagra Not necessarily. It mayn't find the cycle in first go. So, we can't say it's of O(n).
brainiak First learn what's an 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]sarath_chandra99 in while loop instead of fast if i replace slow, its not working..can u tell me y? and y did u use (fast != null && fast.next != null) , just (fast!=null) is giving output
email109 Indeed, this solution is correct. Problem is - it doesn't pass the test. I guess their test is broken for this problem.
diegocast04 I have the same issue...
amitmisra Why segmentation error ?
mayank7577 Sir this solution is not working it is giving null pointer exception!
amitmisra bool has_cycle(SinglyLinkedListNode* head) { SinglyLinkedListNode* p=head; SinglyLinkedListNode* q=head; if(p==NULL) return false; while(p!=NULL && p->next!=NULL) { q=q->next; p=p->next->next; if(p==q) return true; } return false; }amitmisra Here is the solution that works fine for me. The while condition is important here otherwise pointer error will arise
mayank7577 This solution is not working in Java! Compiler message 'Wrong Answer'.
manish2421 this is not working on list of 1213512135. please provide solution
viragjain_vj I write the code in the same way, but its failing for the testcases and when i paste the same code written by you, still the testcase are failing. Is there any bug in the testcases? May be their expected output written wrong if your code is correct.
nihar_turumella hey for the while check, I used slow instead of the fast ... basically slow !=Null && slow.next!=Null and except for the first two cases, the ret failed, why?
JavistSetia 5/7 test cases failed using this algo!!!!!
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; }
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;
Zolbayar The predefined codes in Java 7, Javascript, Python 2, Python 3 are not working!
kapploneon Is the testcase 1 failing. I am facing similar problem, I think my solution in Java is correct. I tried debugging.
Zolbayar You should try it with C# or another language.
kapploneon You mean to check my logic is correct or not?
c4ar1_1lo0s5 Thank god I saw your comment, I tried my approach in C and it works now, I spent almost three hours thinking what was wrong with my code. Trying to debug Java with custom input is useless too.
neonbjb The Java pre-defined parser for this problem is broken - use another language until it works.
Thuxg The codes has bug ( Python2 and Python3 ): Sorry: TabError: inconsistent use of tabs and spaces in indentation (solution.py, line 80)
I cant compile it !!!
emarsc The Node JS code is broken, the python code is broken, and I am getting incorrect results with a java function that I know works. This new site layout is not good.
rjbcc58 Same, I am using java HashSet to check if node was previously seen (not fast/slow pointer algorithm), but cannot get correct results.
shofi384 I have tried the Java HashSet as well as the slow and fast node approach; both gave me wrong answer. I looked into the main method; I think the main method is never creating a cycle but appending each node to the end of the list. That's why test for cycle fails. Though the same algo and similar functions worked in C++
anikakelhanka I also faced the same problem. Even used the editorial solution. That failed too.
amarbatp Yeah, it is exactly same to me. I've tried with 3 different approaches, no difference. Hidden code looks not creating any cycle anyway. Did anyone overcome this issue?
kapploneon Nope
amarbatp Thanks for answering, Kapploneon. Finally, I've accomplished it by writing my code on C++ instead Java. Pre-made code for Java has some problem, but it is well developed for C++.
amarbatp RESOLVED: After struggling with Java for a while, finally I've wrote my code on C++ and successfully submitted. It seems like hidden Java code for this problem is not developed well, so you won't have chance to accomplish it on Java.
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.
kapploneon Hey I applied similar solution tried with storing Node as well as with hashcode() of the node both are failing for the testcase 1. I don't know why. Compiler message: Wrong answer. output 0, expected 1.
Though I tried debbugging and none of the elements repeat.
m_balajee [deleted]m_balajee [deleted]m_balajee What if the node points to itself?
Abushawish [deleted]
DanHaggard [deleted]
pechavarin_cs I am getting "Sorry: TabError: inconsistent use of tabs and spaces in indentation", in a line that i cannot edit.
vidur2wadhwa I am using python language and i keep on getting this error:- Sorry: IndentationError: expected an indented block (solution.py, line 83)
Even though this line is prewritten in the solution and i cannot edit it. It is really frustrating and I dont know what to do can somebody provide a solution???
Sort 460 Discussions, By:
Please Login in order to post a comment