Home > Applied Algorithms, Linked List > Find the starting point of a Cycle in a Linked List.

Find the starting point of a Cycle in a Linked List.

You have been given a linked list which has a loop (or cycle) in it. You are supposed to find the starting point of this cycle. Please note that this is a singly linked list.

First of all, putting aside the matter of detecting the starting point of the loop, tell me how would you detect a loop in a linked list? This is pretty simple and you’ll love it if you haven’t heard of the solution before.

What you need to do is take 2 pointers at the start of the linked list. Now at every turn, move one of the pointers to the next position, and move the other pointer forward by 2 positions. If these pointers meet at a certain point, i.e., pointer1=pointer2, you know that there is a loop in a linked list. Otherwise, not.

Let me take an example,

In the image shown above, we take 2 pointers, point1 and point2, both pointing to node 1 (start) of the linked list.

Now at step 1, move point1 to node 2, point2 to node3

Next, move point1 to node 3, point2 to node 5

Next, move point1 to node 4, point2 to node 7

Next, move point1 to node 5, point2 to node 4 (since we move 7->8 and then 8->4 while moving 2 nodes forward)

Next, move point1 to node 6, point2 to node 6

Oh! My pointers just met! That means I have a loop in my linked list. 🙂

Now coming to the matter of finding the starting point of the loop –

When your pointers meet, you’ll be as many nodes away from the starting point of the loop as the starting of the loop is away from the start of the linked list.

This means, the start of my loop is as far from 6 as from 1. (That is true, as you can see)

To get this start of loop, put one of your 2 pointers at the start and now start moving both pointers forward by 1. When they meet, you know that this is your loop’s starting point. 🙂

Example, leave point1 at 6. Make point2 equal to start (node 1). Now moving each forward by 1,

Move point1 to node 7, point2 to node 2

Move point1 to node 8, point2 to node 3

Move point1 to node 4, point2 to node 4

They clashed! This is the start of your linked list! 😉

More questions on linked list on their way! Don’t go!

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

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

%d bloggers like this: