CareerCup

1. find where the slow and fast pointers meet.
2. split the LL at that point. So that the loop is removed and now the "6" becomes a "Y" (Think about it and convince yourself that it infact becomes a "Y"
3. Now it becomes a question of finding intersection point of the two LL's .
4. Once you find the intersecting point. Traverse both lists once each.
5. Length of the original LL = The uncommon nodes (from both the LL's) + common nodes counted only once (the tail of the "Y")
6. Join the split ends back together to get a "6" .

A few restrictions: Run time complexity is O (N) and memory has to be CONSTANT.

2 pointers
incr one by +1
incr other by +2
they will frist meet in N iterations

2 pointers
incr one by +1
incr other by +2
they will frist meet in N iterations

2 pointers
incr one by +1
incr other by +2
they will frist meet in N iterations

the step here is to find the length of list. not to see whetehr circle s present.

Use hashing for each node you traverse keep incrementing the node count. The moment the new node clashes in the hash table, you stop traversing and return the count. This has the execution time complexity of O(N) and the space complexity of O(N)

Ravi. You approach only works when the shape is like 6 or 0.

It doesn't work for cases when the shape is like 8 or @.

However, I don't know if 8 or @ are valid cases. Or else, maintaining a hash for pointers will do.

Nil

Length of such a list = Length of the loop + Length of the non-loop segment.

Have a flag in the node, set it to true once you visit it and increment the counter.
Finally the counter is the size of the list!!