Loopy Linked list

How
 can 
one 
determine
 whether 
a 
singly
 linked
list 
has 
a 
cycle in O(n) complexity?

Solution:

Good 
answer: 
Keep 
track 
of 
two 
pointers 
in 
the 
linked
list, 
and
 start 
them
 at 
the beginning
 of 
the 
linked
list. 

At
 each 
iteration
 of
 the 
algorithm,
 advance
 the 
first pointer 
by 
one 
node
 and
 the 
second 
pointer 
by
 two
 nodes. 

If 
the 
two
 pointers 
are ever the 
same
 (other 
than 
at 
the 
beginning 
of
 the
 algorithm),
 then
 there
 is
a 
cycle. 

If a
 pointer 
ever 
reaches 
the 
end
 of 
the 
linked
list 
before 
the
 pointers 
are
 the
 same,
 then 
there 
is 
no 
cycle. 

Actually, 
the
 pointers 
need
 not 
move 
one
 and
 two
 nodes 
at 
a
time; 
it 
is 
only 
necessary 
that 
the 
pointers 
move
 at 
different
rates.

This
takes 
O(n)
 time.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s