## 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!