How to find the length of a linked list that is having cycles in it?

Posted by Bragaadeesh on Stack Overflow See other posts from Stack Overflow or by Bragaadeesh
Published on 2010-05-05T12:08:25Z Indexed on 2010/05/05 12:28 UTC
Read the original article Hit count: 129

Filed under:

linked-list

|

algorithm

|

cycle

|

length

|

interview-questions

This was one of the interview questions asked. How to find the length of a linked list that is having cycle in it. I know how to calculate whether a linked list has a cycle or not using Hare and Tortoise technique. I even know how to calculate the length by storing the addresses in a hashset.

But what I was not able to tell is how to calculate the length of the linked list without using a external space of O(n). Please help me. Thanks.

© Stack Overflow or respective owner

Related posts about linked-list

how to copy one linked list contents to another linked list

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I have been given list L1, L2. L1 contains 1,2,3 and L2 contains 4,5,6. how do i copy the contents from L2 to the end of L1 so in the end L1 contains 1,2,3,4,5,6. any suggestions? >>> More
Linked list and doubly linked list examples

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm looking for a good understandable example in c++ with differences. Does the header file <list.h> provide both or should I look somewhere else? >>> More
Replace LinkedList element value through LinkedList.Enumerator

as seen on Stack Overflow - Search for 'Stack Overflow'
I realize there are no way for me to replace value through LinkedList.Enumerator. For instead, I try to port the below Java code to C# // Java ListIterator<Double> itr1 = linkedList1.listIterator(); ListIterator<Double> itr2 = linkedList2.listIterator(); … >>> More
Handwritten linked list is segfaulting and I don't understand why

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi I was working on a bit of fun, making an interface to run gnuplot from within c++, and for some reason the my linked list implementation fails. The code below fails on the line plots-append(&plot). Stepping through the code I discovered that for some reason the destructor ~John() is called immediately… >>> More
removeFirst and addLast methods of LinkedList Class are Unknown

as seen on Stack Overflow - Search for 'Stack Overflow'
I have a problem with my code in C# . if i click in compiler button , I get the following errors 'System.Collections.Generic.LinkedList<int?>' does not contain a definition for 'removeFirst' and no extension method 'removeFirst' accepting a first argument of type 'System.Collections… >>> More

Related posts about algorithm

Jpeg Algorithm vs BMP Algorithm?

as seen on Super User - Search for 'Super User'
I'm just wonder, what the differences are between creating a BMP file algorithm and JPG file algorithm ? If you know the others images' format algorithm, please post them. Thanks. >>> More
word disambiguation algorithm (Lesk algorithm)

as seen on Stack Overflow - Search for 'Stack Overflow'
Hii.. Can anybody help me to find an algorithm in Java code to find synonyms of a search word based on the context and I want to implement the algorithm with WordNet database. For example, "I am running a Java program". From the context, I want to find the synonyms for the word "running", but the… >>> More
Search algorithm (with a sort algorithm already implemented)

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello, Im doing a Java application and Im facing some doubts in which concerns performance. I have a PriorityQueue which guarantees me the element removed is the one with greater priority. That PriorityQueue has instances of class Event (which implements Comparable interface). Each Event is associated… >>> More
Is there any algorithm for finding LINES by PIXEL COLORS on picture?

as seen on Stack Overflow - Search for 'Stack Overflow'
So I have Image like this I want to get something like this (I hevent drawn all lines I want but I hope you can get my idea) I need algorithm for finding all straight lines on it by just reading colors of pixels. No hard math, no Haar, no Hough. Some algorithm which would be based on points… >>> More
collsion issues with quadtree [on hold]

as seen on Game Development - Search for 'Game Development'
So i implemented a Quad tree in Java for my 2D game and everything works fine except for when i run my collision detection algorithm, which checks if a object has hit another object and which side it hit.My problem is 80% of the time the collision algorithm works but sometimes the objects just go… >>> More