## Cycle Detection

- CL
clacrone + 27 comments 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; }`

- CC
Tofurkey + 1 comment Great solution and explanation!

- BP
byronrpv_rckr + 1 comment 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 + 0 comments 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 + 0 comments nice one

- JV
jens_vanderhaeg1 + 1 comment What would you say the time complexity is? O(N)?

- MA
Abushawish + 2 comments Yes, O(N) because you have to go through every element regardless of factor.

hammeramr + 8 comments 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; }

- E
ekuznets + 0 comments [deleted] khandelwalnites1 + 0 comments [deleted]- MB
Madhav_Bhatt + 0 comments 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 + 1 comment 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.

- AM
ashu_msr19 + 0 comments 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 + 0 comments [deleted]- AM
ashu_msr19 + 1 comment wow! man ur comment was incredibly stupid ,its good that at least u can code.

- MP
maitrey2112 + 0 comments Wow!. Man your grammar is incredibly stupid and incorrect , it's good you can at least code.

dharmikp572 + 0 comments I did similar thing in java XD

- JS
jasmeet17 + 0 comments Can some body explain why there are 10 downvotes?

abhinavkushagra + 0 comments Not necessarily. It mayn't find the cycle in first go. So, we can't say it's of O(n).

nike3801 + 0 comments Nice explanation.

- DA
askarovdaulet + 0 comments 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.

- HK
hekuang + 2 comments But what if the last pointer points back to the first one?

- DA
askarovdaulet + 0 comments [deleted] - DA
askarovdaulet + 1 comment 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.

- HK
hekuang + 0 comments Right! Thanks for the explanation.

ethan_sec + 5 comments 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 + 5 comments 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

- SP
shubhampachori6 + 1 comment What if two nodes in a list have the same data in two nodes but they are not in a cycle?

ishabandi + 4 comments 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 + 0 comments [deleted]adityaloshali1 + 1 comment 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 + 2 comments Yes! yours is cleaner. too many redundant lines in mine. What about the complexity? Will it work under huge lists?

adityaloshali1 + 0 comments 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 + 0 comments 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.

- JC
jcflorezr + 0 comments [deleted] ojhasaurabh2099 + 0 comments [deleted]

- GI
gregigusa + 0 comments [deleted] vshantam + 0 comments 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

- MP
maitrey2112 + 0 comments 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

- HW
henryjw + 0 comments `visited = set()`

It's probably a good idea to use sets instead of arrays for lookups since the difference is

`O(n)`

vs`O(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.

- DP
DishaParwani + 0 comments [deleted] - AS
NorthernLight + 0 comments 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 + 0 comments 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

`Â¯\_(ãƒ„)_/Â¯`

- HW
HHWWHH + 0 comments 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

- MR
positivedeist_07 + 0 comments 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!!

anirudh04 + 1 comment If I use "while(fast.next!=null && fast!=null)" It's not working.Can anyone explain this?

- RP
rajp4690 + 0 comments you should check "fast != null" first because if fast is null then as per your condition it will be like "null.next != null" and you can't check null.next that is why its not working.

alpha52omega41 + 0 comments Also known as Flyod Cycle finding algorithm..

ishabandi + 0 comments I hope my understanding is correct.

You are just checking if any of the 'next' are same by using to iterables?

- BR
benraw11 + 0 comments [deleted] - KM
mjhere + 0 comments Good solution. Thank you:)

- PP
chanchanman + 1 comment Yes! The Floyd Algorithm! :D

- ES
elaines + 0 comments Why it's related to this algo? :) I checked floyd, but didn't get any clue of their similarity. could you explain a bit?

- M
MoulikGupta + 0 comments The old "tortoise and the hare" problem in python.

- M
MoulikGupta + 0 comments 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 + 1 comment If there are just two nodes in the linked list with a cycle, how will it work?

yash324 + 0 comments slow will increment by 1 and fast will increment by 2, they will be the same every alternate loop.

abhinavmane113 + 0 comments Impressive solution. Btw Add null check for fast pointer after if statement in while loop, in some cases segmentaion fault occurs.

rollins_jackson + 0 comments Is this classic CS material or something?

- SJ
prempaljee111 + 0 comments 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 + 0 comments Easy stroy and deep Zen. Incredible!

ShubhamK271999 + 1 comment 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 + 1 comment (-

*_*_-) Seriously? You're kidding us? You lose your O(1) the time you used while loop.ShubhamK271999 + 1 comment 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 + 1 comment 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 + 1 comment 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 + 0 comments Not exactly! :\

- AK
kharcheavinash11 + 0 comments [deleted] - AM
andy17 + 0 comments 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 + 0 comments 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; }

- GM
gan_mit08 + 0 comments [deleted]

hshah8831 + 6 comments 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 + 3 comments 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.- SC
sothy_chan + 2 comments 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 + 3 comments 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.- AK
ak47gyani + 1 comment I dint understand. If you start both pointers at head and increment them at different speeds, then why ll it fail?

mohitaggarwal516 + 1 comment it will fail in the first case only. It wont go further.

- KH
krishzinx + 0 comments cant we first increament the pointers and then check??

- VK
varad2512 + 0 comments The simpler way just change the way you compare.Instead of node->data compare the node's addresses.Works!

- NN
nijwm21 + 0 comments 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 + 0 comments 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 + 5 comments 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;`

- VH
virajh + 1 comment If the code above is your solution, it is very incorrect since the assumption is nodes will not be greater than 100.

- TE
t_egginton + 0 comments 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 + 0 comments what if cycling has been done twice??

manni_reies + 0 comments LOL, I came up with the same solution, it's a cheat solution thought lol :P

- YP
Yeetesh + 0 comments haha i came to the same solution but it felt really noob to use it :P

positivedeist_07 + 0 comments Can u pls explain what u did here corresponds to the question asked?

RaoPisay + 0 comments Well I did it in java using hashCode()

- JG
ja5hga1a + 2 comments Was this issue resolved or the solution ever found??? I am facing the same issue. Exactly the same output as yours.

- SC
sothy_chan + 1 comment 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.

- AG
agodfrey3 + 0 comments 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 + 0 comments 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 + 0 comments 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 + 0 comments [deleted]singh_mona + 2 comments 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 + 0 comments hey,

`if(head->next=head)`

is not mean to be

`if(head->next==head)`

you are using

`assignment`

instead of`equality`

.Also, your while loop is evaluating

`slow`

and`slow->next`

that are pointers to memory address, they are`!= 0`

(that is, true). I guess you mean`while (slow != NULL && slow->next != NULL)`

, right? Finally,`fast`

reaches the end of the list before slow (if it does not contains cycles), so you should check for`fast`

in the while expression, don't you?Cheers!

- RR
rishindrareddy + 0 comments [deleted]

Piyushpky + 0 comments 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 + 5 comments 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 + 0 comments Wow, that's something unique

kr_abhinav + 0 comments What you are talking about is floyd-cycle finding algo. If you found it yourself,commendable!

krishnkant_ + 3 comments 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 + 0 comments @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 + 0 comments Smart !

- GP
gowthamprakaash1 + 0 comments true logic is correct not a cheat if it contains cycle,then it will cycle cycle cycle....

nripesh21 + 0 comments elegant!

ujjwalsaxena + 0 comments 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; }

- W
WeilanYang + 7 comments 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 0`

- AK
arunkumar_123 + 0 comments 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 + 0 comments I did the same, came here to see if there was a better way... was not disappointed !

- MA
Abushawish + 2 comments 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; }

- MB
m_balajee + 0 comments [deleted] saif01md + 1 comment 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.

- NK
festmeny + 0 comments 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.

- MB
m_balajee + 0 comments [deleted] - MB
m_balajee + 0 comments [deleted] - MB
m_balajee + 1 comment What if the node points to itself?

- MA
Abushawish + 0 comments [deleted]

- D
DanHaggard + 0 comments [deleted]

manikhanuja1981 + 0 comments 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; }

- NA
nasser85 + 0 comments If the

`head`

can 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; } }

- KS
kaivanshah1663 + 0 comments **I Guess this will be the simplest in python....**def has_cycle(head): if head.next == None: return 0 else: return 1

nandkarthik + 0 comments Important: I was checking only the values. But, it seems like we should check by reference not by data value.

- PS
Parthasch + 1 comment 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;`

}

- PA
2010prashant + 0 comments 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;

}

- AR
anshuman_rohella + 1 comment 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 }

- YU
yilmazneo + 1 comment 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.

- AR
anshuman_rohella + 0 comments 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