Data Structures: Cycles in a Linked List

hi I'm Gail lock McDow author of cracking the coding interview today we're going to cover a classic interview question given a link list how would you detect a cycle in the list this is a classic link list question possibly the most common interview question for link lists and also demonstrates a really common technique so the question is as follows you have a link list and you want to figure out if it contains a cycle a cycle means that the link list actually Loops back on itself not necessarily to the beginning of the link list but somewhere in the link list so one way of solving it is that you walk through the link list and if you and you mark each node and if you've seen if you get to know that you've seen before then you know that it contains a cycle that's a great technique if you can modify the link list but if you can't that won't really work so here's another way of thinking about it imagine the link list was like a racetrack and you driving around it well one way you know that you have a a link a loop in the in the list is if you've seen somewhere that you've been before again that's kind of the first technique another way is imagine there are two cars driving around this racetrack if the cars drive at different speeds then you know that they will if there's a loop they they will eventually Collide they will eventually pass each other and we can do this exact technique on a link list so we can have two pointers moving through the link list at different speeds one Moving Two nodes for every time time the other pointer moves one note they will eventually Collide if there's a loop if there is no Loop then one will one or well both of them eventually will get to the end of the link list so let's try out this technique so we're going to call this method has cycle and it's going to take in a head node and then it's going to return a Boolean if it does in fact contain a cycle so first of all let's cover our null pointer check so if head is null then certainly there's no cycle other wise what we want to do is have two pointers one I'll call fast fast moves twice as fast as slow one and I'll start as a first approach having them both point to the head of the link list now we want to move through the link list so a fast does not equal null and slow does not equal null then if they've collided if fast and slow are at the same node then we know we found a cycle otherwise oops move each of these now fast is going to want to move two jumps for each time slow moves once so fast is going to move two so move fast to fast. next. next and slow is just going to move by one and if they get to the end then we return if we get get to the end and we haven't found a link a loop then they return false so before we run this let's think and make sure this code really makes sense so let's walk through it well first fast and slow are going to point to head and then we're going to get in here and say if fast is slow well that'll be a mistake because they're both already starting off the head so the very beginning L 16 will return true so actually what we want to do is start them off at slightly different points so fast is actually going to start off at the second node and slow is going to start off at the first and then let's make sure we don't have null pointer checks null pointer exceptions possible so let's look at all the points we have pointer so we have fast. next fast equals head. next head won't be null so that'll be okay then here what about this one what we're calling fast. next. nextt fast won't be null but fast. nextt might be null so let's throw that in as a case so we actually want to stop if fast. next does not equal no okay now I think our code looks pretty good fast will not be null fast. next will not be null so fast. next and X will be fine slow will will equal uh will not equal null so that'll be okay now it's possible that slow that this exception that this if statement is unnecessary you know it won't really cause a problem so I'll leave that in so now let's try running our code okay so I'm going to click this run code button and see what what happens perfect we passed the the test case so now I'm going to go ahead and submit our code great our code works so to walk through it again we set fast and slow fast to the second node and slow to the very first node then we walk through it as long as fast fast. next and and slow is not null then if they've collided then we know there's a loop otherwise move fast by one and then slow by one sorry fast by two and then slow by one if they get to the end and they haven't collided then we know that we can just return false there is no Loop now that you've seen this technique think about applying this in the future on other link list questions