Data Structures: Cycles in a Linked List
Data Structures: Cycles in a Linked List
Learn how to solve the most common interview question for Linked Lists. This video is a part of HackerRank’s Cracking The Coding Interview Tutorial with Gayle Laakmann McDowell. http://www.hackerrank.com/domains/tut…
Content
0 -> Hi, I'm Gayle Laakmann McDowell, author of Cracking the Coding Interview. Today
3.659 -> we're going to cover a classic interview
question: given a linked list how to
8.189 -> detect a cycle in the list.
10.17 -> This is a classic linked list question
possibly the most common interview
14.309 -> question for linked lists, and also
demonstrates a really common technique.
18.09 -> So the question is as follows: you have a
linked list and you want to figure out
22.439 -> if it contains a cycle. A cycle means
that the linked list actually loops back
26.64 -> on itself, not necessarily to the
beginning of the linked list but
30.09 -> somewhere in the linked list. So one way
of solving it is that you walk through
34.98 -> the linked list and you mark
each node. And if you've seen, if you get
39.78 -> to know that you've seen before then you
know that it contains a cycle. That's a
43.62 -> great technique if you can modify the
linked list. But if you can't that won't
48.57 -> really work. So here's another way of
thinking about it.
52.05 -> Imagine the linked list was like a
racetrack and you're driving around it.
56.67 -> Well one way you know that you have a
link, a loop in the in the list, is if you've
61.199 -> seen somewhere that you've been before.
62.91 -> Again, that's kind of the first technique.
Another way is imagine there are two
67.08 -> cars driving around this racetrack. If
the cars drive at different speeds
73.229 -> then you know that they will, if there's
a loop, they they will eventually collide,
77.97 -> they will eventually pass each other. And
we can do this exact technique on a
83.189 -> linked list. So we can have two pointers
moving through the linked list at
86.67 -> different speeds, one moving two nodes
for every time the other pointer moves
92.28 -> one node. They will eventually collide if
there's a loop. If there is no loop then
97.14 -> one will, one or both of them eventually,
will get to the end of the linked list.
100.68 -> Let's try out this technique. So we're
going to call this method has cycle,
107.3 -> and it's going to take in a head node and
then it's going to return a boolean if
112.16 -> it does in fact contain a cycle. So first of
all let's cover our null pointer check. So if head is
116.57 -> null then certainly there's no cycle.
119.69 -> Otherwise what we'll want to do is have two pointers, 1 i'll call fast. Fast moves
126.71 -> twice as fast as the slow one. And I'll start as the
first approach having them both point to the
134 -> head of the linked list. Now we want to
move through the linked list. So while fast is
143.51 -> does not equal null, and slow does not equal
null, then if they've collided, if fast and
151.85 -> slow are at the same node, then we know
we've found a cycle. Otherwise,
158.45 -> oops, move each of these. Now fast is
going to want to move 2 jumps for each
165.05 -> time slow moves once. So fast is going to
move 2 to move fast to fast dot next dot
170.15 -> next and slow is just going to move by
one. And if they get to the end then we
176.93 -> return, if you get it to the end and we
haven't found a link, a loop, then they
181.61 -> return false.
182.72 -> So before we run this let's think and
make sure this code really make sense.
186.62 -> Let's walk through it. Well first fast
and slow are going to point to head and then
191.63 -> we're going to get in here and say if
fast, if slow.
194.42 -> Well that'll be a mistake because
they're both already starting off the
197.66 -> head so at the very beginning, line 16,
will return true. So actually what we
202.25 -> want to do is start them off at slightly
different points. So fast is actually going to
206.239 -> start off at the second node and slow is
going to start off on the first. And then
211.07 -> let's make sure we don't have null pointer checks, null pointer exceptions possible. So let's
216.709 -> look at all the points we have pointers.
So we have fast dot next fast equals head dot
221.63 -> next head won't be null, so that will be
okay, then here what about this one?
227.39 -> We're calling fast dot next dot next. Fast
won't be null but fast dot next might be null.
232.519 -> Let's throw that in as a case.
235.45 -> So we actually want to stop if fast dot
next does not equal null.
241.09 -> Ok, now I think our code looks pretty
good. Fast will not be null, fast dot next will not be null, so
247.3 -> fast dot next dot next will be fine, slow
will equal, will not equal null, so
253.33 -> that'll be ok. Now it's possible that
slow, that this exception, that this if
258.669 -> statement is unnecessary.
260.44 -> You know, it won't really cause a problem
so I'll leave that in. So now let's try
264.639 -> running our code.
266.68 -> Ok so I'm going to click this run code
button and see what happens.
270.669 -> Perfect. We passed the test case so now
I'm going to go ahead and submit our
276.97 -> code. Great. Our code works. So to walk
through it again, we set fast and slow,
283.36 -> fast to the second node, and slow to the
very first node, then we walk through it
288.31 -> as long as fast, fast dot next, and
slow is not null then if they've
293.29 -> collided then we know there's a loop.
Otherwise move fast by one and then
297.76 -> slow by one.
299.08 -> Sorry, fast by two and then slow
by one. If they get to the end and they
302.86 -> haven't collided then we know that we
can just return false, there is no loop.
307.78 -> Now that you've seen this technique
think about applying this in the future
311.56 -> on other linked list questions.
Source: https://www.youtube.com/watch?v=MFOAbpfrJ8g