Here we are going to use runner techniques, where there will be a two pointers slow and fast. Fast will going to take double steps then slow one, Lets see in below image.

As per the above image, you can see loops starts with Node (4), Lets assume distance from Node(1) to Node(3) is “**m**” and length of loop is “**n**“, Since we have two nodes (Slow and Fast), both will meet at some point in loop. Lets assume that point is at “k” distance from Node(4).

So now we have below three distances.

n = Length of cycle

m = Distance between first node of cycle (Node(4)) and head of linkedlist (Node(1))

k = Distance of point where slow and fast node meets.

Now lets assume distance traveled by Slow and Fast pointer as per below.

`S = m+k+(R1)*n`

– R1 is number of round made by Slow pointer in a loop before it meets to Fast pointer.

`F = m+k+(R2)*n`

– R2 is number of round made by Fast pointer in a loop before it meets to Slow pointer.

Since Fast pointer is twice faster than Slow pointer.

`F = 2S`

F = 2( m+k+(R1)*n )

m+k+(R2)*n = 2( m+k+(R1)*n )

m+k = (R2-2R1) n (This is IMP Step)

As per above equation **m+k** is equal to some number of loops.

Lets assume **(R2-2R1) = 1**.

`m+k = (R2-2R1) n`

m+k = (1)n

Here m+k is equal to one entire loop.

It means if we travel **m+k** is equivalent to travel * one entire loop *, Here one entire loop means start from Node(4) and end to Node(4).

Now we are going to move slow node at first position and now move fast and slow both node at same speed.

Here distance travelled by slow node is as per below.

`S = m`

At same time distance travelled by Fast node is also **m** but fast node started from **k** distance so total will be **k+m**

`F = m+k`

`so as per above m+k is one entire loop (n). `

. So because of this when Slow will reach to Node(4) at same time Fast will finished its one loop and will reach to same Node(4)*[m+k = (1)n]*

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
package com.omt.learn.algo; import com.omt.learn.algo.util.linkedlist.LinkedListNode; /** * Created by omt on 3/26/17. */ public class LinkedListLoopDetect { public static void main(String args[]) { LinkedListNode ln = generateLinkedListNode(); System.out.println("Start node in loop :" + findLoopAndStartNode(ln).value); } private static LinkedListNode findLoopAndStartNode(LinkedListNode node) { LinkedListNode slowNode = node.next; LinkedListNode fastNode = node.next.next; while (slowNode != null && fastNode != null) { if (slowNode == fastNode) { break; } slowNode = slowNode.next; fastNode = fastNode.next.next; } if (slowNode == null || fastNode == null) { return null; } else { slowNode = node; while (slowNode != null && fastNode != null) { if (slowNode == fastNode) { return slowNode; } slowNode = slowNode.next; fastNode = fastNode.next; } } return null; } private static LinkedListNode generateLinkedListNode() { LinkedListNode n1 = new LinkedListNode(1); LinkedListNode n2 = new LinkedListNode(2); LinkedListNode n3 = new LinkedListNode(3); n1.next = n2; n2.next = n3; LinkedListNode n4 = new LinkedListNode(4); LinkedListNode n5 = new LinkedListNode(5); LinkedListNode n6 = new LinkedListNode(6); LinkedListNode n7 = new LinkedListNode(7); LinkedListNode n8 = new LinkedListNode(8); LinkedListNode n9 = new LinkedListNode(9); n3.next = n4; n4.next = n5; n5.next = n6; n6.next = n7; n7.next = n8; n8.next = n9; n9.next = n4; return n1; } } |

You must be logged in to post a comment.