# Linked Lists: Detect a Cycle

# Linked Lists: Detect a Cycle

vmarica + 27 comments Java solution using fast and slow pointers, no need for a HashSet.

boolean hasCycle(Node head) { if (head == null) return false; Node slow = head; Node fast = head.next; while (slow != fast) { if (fast == null || fast.next == null) return false; slow = slow.next; fast = fast.next.next; } return true; }

psomers + 1 comment I feel like I'm missing something but how would this detect larger loops?

vmarica + 2 comments If a loop exists, then the fast pointer will eventually end up behind the slow pointer. The fast pointer will then catch up to the slow pointer, detecting the loop. This will always happen, no matter the size of the loop.

nyxcalamity + 1 comment It will also cycle the loop multiple times redundantly consuming CPU and IO :P

phillipnguyen + 1 comment I think the fast pointer is guaranteed to cycle through the loop exactly exactly twice before it meets the slow pointer, so it's not really that bad.

hasunamarasekara + 5 comments How do you know that the fast pointer will go through the loop only twice? Written out it makes sense, but do you know of any good sources suppourting that?

phillipnguyen + 2 comments Let f(i) = the memory address of the node that is a distance i from the head of the list. So f(0) = head, f(1) = head->next, and so on. If there is a cycle of length L that starts at node N in the list, then f(i) = f(i + kL) for all i >= N and all k >= 0 by periodicity.

In particular, assuming the slow and fast pointers meet, we have f(i) = f(2i) which means that 2i = i + kL or i = kL. So the slow pointer is equal to the fast pointer for all values of i = kL where kL >= N. The first time they meet is the smallest such kL.

So my earlier statement isn't strictly true the way that I wrote it -- if N is much larger than L, then the fast pointer will spin around in the cycle several times while it waits for the slow pointer to just reach the start of the cycle. But once the slow pointer does get to the cycle, it will reach the smallest kL >= N somewhere during its first traversal around the cycle. Since the fast pointer is going twice at fast, it will only travel around the cycle at most twice during this time.

The time complexity is O(kL) = O(N + L); that is O(N) for the slow pointer to reach the cycle, plus O(L) for the slow pointer to reach the meeting point somewhere during its first time around the loop.

hasunamarasekara + 0 comments Great explanation, thank you!

jorgekasa + 0 comments This is another great source to understand the algorithm

artem_pyanykh + 0 comments Another explanation using

**modular arithmetic**. Let's assume that:**slow pointer**has reached the beginning of the cycle (at index`0`

)**fast pointer**was somewhere within the cycle (at index`k`

)**cycle length**is`n`

.

Then the question is how many iterations

`i`

is needed to satisfy the equationi == k + 2i (mod n)

Setting

`i := n - k`

we get- lhs:
`n - k (mod n)`

- rhs:
`k + 2(n - k) = 2n - k == n - k (mod n)`

So, we need

`n - k`

iteration for two pointers to meet within the cycle.Cheers!

isharth + 0 comments My nooby explanation: Slow pointer speed = 1 node per unit time = n. Fast pointer speed = 2 node per unit time =2n. Stick the slow pointer to the start of the loop then fast pointer's relative speed= n. Let loop be consisting of m nodes. Then fast pointer takes 1 round covering m nodes to meet slow pointer at speed n. At its original speed 2n, it must take 2 rounds!! :-o

Paul_Denton + 0 comments [deleted]

cjoatkinson + 3 comments Did something similar but just changed around the checks, unfortunatley I keep hitting a null pointer and I'm unsure why. Any thoughts?

boolean hasCycle(Node head) {

`if(head==null){ return false; }`

Node Fast = head.next; Node Slow = head;

while(Fast.next != null || Fast != null){

`if(Fast == Slow){ return true; } Fast = Fast.next.next; Slow = Slow.next;`

}

return false;

}

P.S. Unfortunatley I can't seem to remember how to set which language I'm using on my comment

aufuray + 1 comment Your while loop should check that both conditions are not NULL, so use the AND (&&) operator to ensure you don't get to the null pointer while(Fast.next != null && Fast != null)

RAaTS31 + 1 comment just change the order, i.e, while(Fast != null && Fast.next != null). bcoz if Fast is already null then Fast.next will give segmentation fault

nihar_turumella + 0 comments Why is and used here and not or? in the while loop also I am getting an error using the slow pointer instead of the fast pointer, why?

rositajane91 + 0 comments Inside the while loop you are trying to access fast.next.next whose value could be null.

syed_adnan_ali_1 + 0 comments Also there is a count. Your number of iterations has to be <= 100

AbhishekVermaIIT + 1 comment **That's a brilliant solution.**Such ideas should be encouraged in "Discussions". I am literally shocked to find such an awesome post buried down on the page because of 0 upvotes. You have my upvote +1 bro.

Thanks a lot for sharing the approach !

guanzo + 1 comment While it is a brilliant solution, it's also a standard and classic one. https://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare. People may be more interested in unorthodox solutions.

AbhishekVermaIIT + 0 comments Perhaps !

I still feel this can benefit someone, hence +1

By the way, thanks for the link :)

ashutoshupreti + 0 comments nice one

tao_zhang + 5 comments For anyone wants to compare this with a HashSet solution:

boolean hasCycle(Node head) { Set<Node> seen = new HashSet<>(); while (head != null) { seen.add(head); head = head.next; if (seen.contains(head)) return true; } return false; }

ju7847 + 0 comments You're essentially modifying the head though which is no good...

ogadeluxe + 1 comment I got this:

boolean hasCycle(Node head) { if (next == null) return false; if (next == head) return true; else { if (head.next != null && next.next != null) { return next.next.hasCycle(head.next); } else { return false; } } }

waseefakhtar + 1 comment I wonder why the line

return next.next.hasCycle(head.next);

is not

return hasCycle(head.next);

instead.

andrewsenner + 0 comments Looks like a condensed version of the tortoise and the hair approach.

raychenon + 1 comment There is no constraint saying the values are unique. With this linear Linked List :

**1->2->2->3->2->null**. The value 2 is in the list 3 times. Your method will return true.sonyakc_2007 + 0 comments Great comment! I was trying to keep track of values in the node but there's nothing stopping two distinct nodes from holding the same int data value. I couldn't comprehend what was wrong with my solution.

polmki99 + 3 comments I did the same in Python. I don't like the hare and tortoise solution.

def has_cycle(head): curr = head seen = set() while curr: if curr in seen: return True seen.add(curr) curr = curr.next return False

churnikorn + 0 comments Was going down the same path. Glad to see the tortoise and hare solution and to now know about it (makes sense), but also prefer this. Likely, it depends on if you're needing to save space or not here.

ahmedelsyd5 + 0 comments that's clean man

anujpriyadarshi + 1 comment I don't know if linked list always contain distinct element or else your code may fail at some point..

famibica + 0 comments The node is an specific object in the memory so it is unique, the only option where it would not work, would be if you are iterating 2 lists and they merge at some point, so you would have the same object in both lists or the same memory addres.

Lovelybone + 0 comments def has_cycle(head): l=[] while head is not None: if head.data in l: return 1 l.append(head.data) head = head.next return 0

tennisonchan + 0 comments Smart! A race of turtle and rabbit. A trade of between calcution(while loop) and storage (Hashset).

Refreshing!

Anvesh_M + 0 comments [deleted]shesanmigz + 0 comments Fantastic solution. Thanks, buddy!

cmichel + 2 comments You can save the initial check by using a

`do-while`

boolean hasCycle(Node head) { Node tortoise = head; Node hare = head; do{ if(hare == null || hare.next == null) return false; hare = hare.next.next; tortoise = tortoise.next; } while(hare != tortoise); return true; }

tao_zhang + 0 comments A do{} while() can always be rewritten to while() do{}. Since whatever is contained in the loop body can always be encapsulated into a routine, do{} while() has never been really popular among professional developers in day-to-day work. To me, personally, I find while() do{} having a condition upfront is clearer and less error prone, therefore is a better practice even with more lines of code, but that's all subjective anyway.

krishnapadia2005 + 0 comments thnx

shawnkmeier + 0 comments In case anyone wants to read more about this algorithm its called "Floyd's cycle-finding algorithm".

https://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare

saumyaj92 + 0 comments Hey, can you take a look at https://www.hackerrank.com/challenges/ctci-linked-list-cycle/forum/comments/253056 and help me find out why this isn't working?

rio_angrybirds + 1 comment it should be if(fast==null && fast.next==null) return false;

nehal_borole + 1 comment [deleted]polmki99 + 0 comments [deleted]

harrysen07 + 1 comment i had the same approach in cpp. But compileris giving segmentation fault. any ideas?

akshaybj0221 + 0 comments I know why.i.e. because there comes a point when you fast->next becomes 0 and you are still doing fast->next->next.

A goof solutin to itis to just do fast->next->next only when fast->next != 0, and return 0 if fast->next is 0. You can see this in the code below. I hope it helps.

bool has_cycle(Node* head) {

`bool ans; if (head == 0) { return 0; } if (head == head->next) { return 1; } Node* tempHead = head; Node* slow = head; Node* fast = head->next; while (tempHead->next != NULL) { slow = slow->next; if (fast->next == 0) { return 0; } fast = fast->next->next; if (slow == fast) { return 1; } tempHead = tempHead->next; } return 0;`

}

bilal_s_hasan + 0 comments Couldn't you add "|| fast.next != slow" to the while loop condition for a more optimal solution? That way it wouldn't have to loop around for a third time if by chance fast skips over the the slow node on the second loop.

kflack + 0 comments Wow, that is a nice solution. I was really blown away by that and I don't usually come across such an elegant solution that makes such instrinsic sense.

Quazar777 + 1 comment You can simply increment a counter variable by 1 every time you do "head=head.next". if the counter goes beyond 100, the list has a loop. If the loop ends before that, it doesn't

def has_cycle(head): if head==None: return False count=0 while head.next!=None: head=head.next count+=1 if count>100: return True return False

mmkos + 1 comment Think about what will happen if the linked list has more than 100 nodes and no loops.

Quazar777 + 1 comment that's why I set the counter for 100, not n. It's a simple hack specifically for this problem.

mmkos + 2 comments Of course it is, it's also completely missing the point of doing an exercise like this.

Watercycle + 0 comments I mostly agree. However, if your data has constraints you should exploit those constraints.

Quazar777 + 1 comment @mmkos the point of the exercise is not to copy paste the editorial solution or pick up a concept from the discussions. I had a different approach, I posted it. And I don't see it missing the point in any way. If the problem has a hole, it is actually expected from a good coder to exploit it.

mmkos + 1 comment I didn't mean to bash your solution or anything like that. Admittedly, I didn't notice the original constraint (i.e. that there are 100 nodes max), so at the time of writing my original post I wasn't sure where the number came from. Therefore, while I understand that now, you could have used a constant instead of a magic number to better convey the idea.

Quazar777 + 1 comment [deleted]keoghpe + 0 comments I solved this problem with the exact same approach.

90% of problem solving is about understanding the problem well. The problem statement says that the length of this list is <= 100 nodes. I think leveraging that is fair game and smart. It results in a less academic solution, but you can't argue with it's effectiveness. This is a really simple and fast way to solve cycle detection for <= 100 nodes.

mkerian10 + 1 comment I have a question if you're still active.

Why are you changing slow at all? Wouldn't it be more efficient to keep slow where it is and just do

`fast.next;`

? Because right now fast gets 1 more node than slow, but it has 5 computations per cycle. But if you kept slow the same and did`fast.next;`

then you'd only do 3 computation per cycle and progress fast at the same speedrfrantsen + 0 comments This is the most efficient solution for certain linked lists whose cycles are guaranteed to cycle back to the beginning, such as a circle. However, imagine a linked list the shape of the number 9, where the first node is at the bottom of the 9, and the "last" node links back to a node in the middle. If slow stayed at the beginning of the list, fast would get stuck since it would never hit the node that slow is waiting at.

rohithraghunath + 1 comment The Floyd's cycle finding algorithm... I have another solution using Stephen Ostermiller's algorithm which also completes in linear time like the Floyd's.

def has_cycle(head): current = head check = None since = 0 since_scale = 0 while (current is current.next): if check is current: return True elif since >= since_scale: check = current since = 0 since_scale = 2*since_scale else: return False since += 1

billw + 0 comments So many problems here. Your loop will only ever run if

`head.next`

points to itself. When it actually does run it would be infinite if`head`

is not`None`

since you never reassign`current`

. Also`since_scale`

is set to 0 and then the only operation you do to it is multiplication, which means it remains 0.Amazingly this passes the test cases which shows how inadequate they are.

Jeff_Chung123 + 0 comments I have a good analogy for this smart solution

/** boolean hasCycle(Node head) { if (head == null) return false; Metaphor,it is like clock,with 1 sec(slow) ,2 sec(fast), slow 1 2 3 4 fast 2 4 6 8 diff 59 58 57 56 **/ //The dynamic algorithm mainly want to enter the clock /** If a loop exists, then the fast pointer will eventually end up behind the slow pointer. The fast pointer will then catch up to the slow pointer, detecting the loop. This will always happen, no matter the size of the loop. Ability is the find the existence of loop,not the location of loop!!! **/ boolean hasCycle(Node head){ Node slow = head; Node fast = head.next; while (slow != fast) { if (fast == null || fast.next == null) return false; slow = slow.next; //the absolute distance between 2 node when looped is always reduce by one fast = fast.next.next; //The smart point is not a static check point(because it only check the static position!) } return true; }

JairAviles + 0 comments Pretty neat solution, however you may define a unique condition of the if within the while due to the fact you have already validate if head was null;

boolean hasCycle(Node head) { if (head == null) return false; Node slow = head; Node fast = head.next; while (slow != fast) { if (fast.next == null) return false; slow = slow.next; fast = fast.next.next; } return true; }

Beeksie + 1 comment Can you explain the logic behind slow and fast?

Watercycle + 2 comments Draw a picture.

# -> D \ # / v # A -> B -> C E # ^ / # \ F <-

Start: slow = A, fast = A

Loop 1: slow = B, fast = C

Loop 2: slow = C, fast = E

Loop 3: slow = D, fast = C

Loop 4: slow = E, fast = E; (slow == fast =>

**cycle found!**)The fast pointer is skipping every other node (fast.next.next) while the slow pointer is stepping through each node one at a time (slow.next). If the fast pointer gets stuck in a cycle, we will eventually reach a point where the slow pointer "catches up" and equals the fast pointer - which can only happen if there's a cycle.

tsdoycheva + 0 comments The best explanation so far. You made it so simple. Thank you

udhavarora2 + 0 comments <3

Kanudo_10 + 0 comments Great... Nice Dude...

keysb + 0 comments Thanks for your solution. For C++ coders would be useful to check validity of fast->next->next pointer to avoid runtime error.

adammoses + 0 comments Tortoise and the hare, great story, even greater code!

spavankumard + 0 comments if the linked list consists of 1,2,3,4,5 it will show nullpointer exception since fast=2,4 then fast!=null and neither is fast.next=null but fast.next.next=null

lightinzide + 0 comments very nice one

ruffdomo + 0 comments paypal

boostedAnimal + 5 comments Always note constraints. You can use two pointer trick as well but remember constraints can matter alot in the real world and you will definitely be penalized for not noticing that the list was only going to be max size 100.

def has_cycle(head): curr = head i = 0 while(i < 100): curr = head.next i += 1 if not curr: return False return True

ToXikyogHurt + 1 comment That '100' looked exploitable to me too, I was lazier still:

def has_cycle(head): try: for i in range(101): head = head.next except: return False return True

Unrelatedly; no PHP version available? Why? Nothing stops you making a simple linked list if you want to. I was looking forward to abusing its built-in behaviour:

class Node { public $data; public $nextNode; } $node = new Node(); $node->data = 'foo'; $node->nextNode = new Node(); $node->nextNode->nextNode = $node; // <- cycle introduced ob_start(); // var_dump() will print '*RECURSION*' in place of a cyclic reference var_dump($node); $s = ob_get_clean(); // ignore closing braces etc $s = str_replace(['}',"\t","\n",' ',"\r"],[''],$s); $s = substr($s,-11,11); echo ($s == '*RECURSION*') ? 1 : 0; // <- cycle detected

scottgauthreaux + 1 comment +1 on the 100 limit. Here's mine in Python:

def has_cycle(head): count = 0 while head.next: head = head.next count += 1 if count > 100: return True return False

subhsamal + 1 comment Why have you taken 100 ? Constraint is list can be of maximum size 100, but does not necessary to be of size 100 always. Please help me to understand. Thanks

scottgauthreaux + 1 comment No matter the size of the list, if it has a cycle, it will eventually iterate more than 100 times. Imagine a list with one node that has itself as a next node. It has a cycle and will loop 100 times and my algorithm will know it has a cycle. This is obviously not an optimal solution, however it is a very simple one. Also, since it is guaranteed to run in O(100) it is actually a constant time solution.

mkr_raju1991 + 2 comments I just tried to add a identifier for each node which can be accessed with O(1) complexity with the help of dictionaries

def has_cycle(head): visited = {} while head: visited[head]=1 if visited.get(head.next,0) != 0: return True head = head.next return False

danyeung091 + 0 comments [deleted]danyeung091 + 1 comment I use Set instead of Dict

def has_cycle1(head): if head == None: return False lmap = set() while head: if head not in lmap: lmap.add(head) else: return True head = head.next return False

raychenon + 1 comment there is no constraint telling that a value cannot be duplicate in the linked list. A possible LL could be :

**1 -> 2 -> 2 -> 3**, it has no cycle. But your algo returns true.gourde_david + 0 comments I don't understand your comment. He never checks the node's data, he checks the memory reference pointer by adding head in the set and not head.data.

declinetostate + 0 comments I approached it the same way. I've just gotten started on HackerRank, but simple solutions that meet the constraints is a trend I'm noticing on the handful of exercises I've tried.

In the real world a robust, simple, and maintainable solution that is done quickly to the given constraints is far more valuable than the "trick" that is a headscratcher to the next owner. It's always a trade-off to consider whether future expandability is worth the effort now vs. accomplishing the current goal and moving on to the next thing. The fancy answer can be added into a well-formed interface when the need is actually there.

khris_kooper + 0 comments I did the same, but neat to learn about this algorithm

mazhuo79 + 0 comments Use a number usually is not a good idea, you may can consider using a new list to contian the data that has been already traversed. Check the code,

def has_cycle(head): alist = [] while head.next is not None: if head.data not in alist: alist.append(head.data) head = head.next else: return True return False

dave_heberer + 2 comments This old chestnut has been around since I first started interviewing. The list constraint makes it so you don't have to go through the trouble of fast slow pointers. you just advance through the list until you hit null or you've done it 101 times. It's three lines.

dave_heberer + 2 comments `int t = 0; while (head != nullptr && t++ < 101) { head = head->next; } return (head != nullptr);`

wramos_wr + 1 comment I'm not entirely sure where you're getting the 101 times part, what if the LL was abnormally large (you don't know the length)

prg5rv + 1 comment Right in the problem it says:

**Constraints:**0 <= list size <= 100

So if we've iterated through the list 101 times, there has to be a cycle.

wramos_wr + 2 comments In an actual interview I don't think you'd have this constraint though, the interviewer would want to see you account for lists with indeterminate sizes

prg5rv + 0 comments Yes, but I was answering where the 101 came from. It's still a smart solution.

dave_heberer + 1 comment I just thought it was such a small constraint that it would work as a solution.

It would be like me passing you an ascii string and length and saying you need to return true if there are duplicates. If you checked the length to see if it was greater than 255 and returned true if so, that is a nice optimization that shows you were thinking instead of regurgitating some memorized solution.

stolenunder1 + 0 comments Actually that solution is great and only runs as long as the linked list is! The only cons is that in order for a cycle to be detected (maybe a cycle occurrs very early in a LARGE list), it HAS to run for the length of the list, where as the Hash style would detect it much faster.

The issue I had with the Hash/dictionary algorithm is that it does use a large amount of memory, or can. Yours only relies on processing a loop, which not only eliminates the space, but runs in O(n) time (of course the Hash/dictionary runs in O(n) as well, but it also potentially adds n memory requirements).

Also, note the ASCII example you gave only works for strings larger than 255. What if I had an ASCII string like "aaa"?? Regardless I love your solution for this problem!

alex_medveshchek + 0 comments Nice solution! :D

realdah + 0 comments This is the same solution I implemented first.. kind of cheating, but passes all test cases for sure.

L0C03L1A5 + 6 comments // A C++ solution with set

#include <set> bool has_cycle(Node* head) { set<Node *> det; if (head == NULL) return false; while (head != NULL) { if (det.find(head) != det.end()) return true; det.insert(head); head = head->next; } return false; }

snydergd + 1 comment I don't think you need to check if head == null before the while loop. If it is null, the while loop won't execute and false will be returned anyway.

abhijeet1403 + 0 comments [deleted]Damayanti + 1 comment @L0C03L1A5 can you please explain the above code

Mjang714 + 0 comments det stores the node that were visited in the set. the first if statement checks to see if the linked list is empty hence why he checls if it is equal to the nullptr/NULL. the while loop checks the whole linked list to see if the element is there. Here we use the set property of no repeated element. That is an element is already in the set then a Node* is returned that is not at the tail of the loop. If the element is not in the set then it will return the tail. So the if statement in the while loop returns anything from det that is not the tail then we return true since it would mean that there was a repeated element.

sdaqiq0 + 0 comments We have to include the set library. I dont think they want us to because the #include <> part is hidden.

jaredmitchell + 2 comments I did something almost the same, just with a Vector. Here's my implementation:

bool has_cycle(Node* head) { vector<Node*> visited; while (head != NULL) { for(int i = 0; i < visited.size(); ++i) if(head == visited[i]) return true; visited.push_back(head); head = head->next; } return false; }

nehal_borole + 1 comment [deleted]fiobe + 0 comments Your code get segfault cause the i variable goes outside the visited array size.

The idea of keeping track of visited nodes is correct, but using an incrementing counter not linked to a specific node of the list is wrong.

If you decide to employ an array, you have some possibilities:

- Store the current node address in the array. For each node of the list, check in the array if its address is there. If not, add it. Complexity is O(n^2).
- Use a hash tabl. The hashing function input is the node address, the output is an array offset. You'll still need to store node addresses (as the key) to handle hash collisions though. Best case complexity is O(n), worst case is O(n^2)).

tq326 + 0 comments Why does the code fails if you put visited outside of the function? I can't seem to understand why it would make any difference at all

jg_goiri + 0 comments You might as well make it an unordered_set for constant time when finding the pointers.

cybosser + 0 comments Clean C++ solution:

Node* next(Node* node) { if (node) node = node->next; return node; } bool has_cycle(Node* head) { Node* slow = next(head); Node* fast = next(next(head)); while (slow != fast) { slow = next(slow); fast = next(next(fast)); } return fast; }

Sort 427 Discussions, By:

Please Login in order to post a comment