detecting the start of a loop in a singly linked link list?

loops linked-list find singly-linked-list cycle-detection
Biswajyoti Das picture Biswajyoti Das · Oct 8, 2009 · Viewed 31.1k times · Source

Is there any way of finding out the start of a loop in a link list using not more than two pointers? I do not want to visit every node and mark it seen and reporting the first node already been seen.Is there any other way to do this?

Answer

balki picture balki · Oct 21, 2010

Step1: Proceed in the usual way, you will use to find the loop, i.e. Have two pointers, increment one in single step and other in two steps, If they both meet in sometime, there is a loop.

Step2: Freeze one pointer where it was and increment the other pointer in one step counting the steps you make and when they both meet again, the count will give you the length of the loop (this is same as counting the number of elements in a circular link list).

Step3: Reset both pointers to the start of the link list, increment one pointer to the length of loop times and then start the second pointer. increment both pointers in one step and when they meet again, it will be the start of the loop (this is same as finding the nth element from the end of the link list).

Related questions

How to determine if a linked list has a cycle using only two memory locations

Does anyone know of an algorithm to find if a linked list loops on itself using only two variables to traverse the list. Say you have a linked list of objects, it doesn't matter what type of object. I have …

Read More
For-each over an array in JavaScript

How can I loop through all the entries in an array using JavaScript? I thought it was something like this: forEach(instance in theArray) Where theArray is my array, but this seems to be incorrect.

Read More
Loop through an array in JavaScript

In Java you can use a for loop to traverse objects in an array as follows: String[] myStringArray = {"Hello", "World"}; for (String s : myStringArray) { // Do something } Can you do the same in JavaScript?

Read More