CareerCup

Suppose, two pointers,fast and slow met at 'node t'.
Now,increment one pointer to point to next node. and the other pointer to start of linked list. Now increment both the pointers until they meet.The meeting point is starting node of cycle. From this you can get the Length of cycle by traversing again since you know the starting point of cycle.

Once we find the point from where the loop begins, it is fairly straight forward to find the length.

geeksforgeeks.org/archives/12225

1. traverse the linked list
2. put next address in a set
3. while putting check for its presence
4. when next is found in the set take its
length

let's examine the problem with every straight solution

1. looping till the end of the linked list ( currentNode -> Next is null ), as the list has loops then we may not reach to this state

2. storing the head node and loop till ( currentNode -> Next == head node ), the cycle may not include the head node for example 1 - 2 - 3 - 4 - 3

3. one possible solution is use a integer variable without initialization which will keep a random value
every time we pass by the node we set this variable to pre-defined value, and if we pass with one node which has this variable set to our pre-defined value then we reach a loop and stop counting at this point

4. One possible solution is use hash for the nodes, whenever we pass with the node we add it to the hash, and if for any node hash[node] == true then we are in cycle and stop counting the length .. this required O(n) addition space

5. One efficient solution is we use the slow/fast pointers where fast pointer moves faster than the slow pointer and after that we will reach a moment where the fast pointer = slow pointer and in this case this is the cyclic node we can start from it and count the nodes till come back to it again, this algorithm calls "Floyed's algorithm for detecting loops, here is the algorithm

int GetLength( Node start_node )
slow_node = fast_node1 = fast_node2 = start_node
do
{
if ( slow_node == fast_node1 Or slow_node == fast_node2 )
break ;
slow_node = slow_node -> next
fast_node1 = fast_node2 -> next
fast_node2 = fast_node1 -> next
} while ( slow_node -> next != NULL );

// now the slow node is a cyclic node we can store it and count till find it again
browser_node = slow_node -> next
int cnt = 1 ;
while ( browser_node != slow_node )
cnt++
browser_node = browser_node -> next

return cnt

careercup.com/question?id=68277

The following algorithm will work
1) Using start and slow pointer to detect the loop.
2) Using temporary variable pointing to the meet point. Another variable traversing through loop and comparing with the temporary variable, find the number of elements in the loop (say k).
3)Now use two pointers first pointing to start of the linked list and second pointing to the k+1 th node, move the pointers. When they meet then that will be the starting point of the loop. So the number of nodes traversed by first node + k, is the total number of nodes in the list.

Just use Floyd's cycle finding algorithm.

Solution uses a slow and fast runner approach. The slow and fast runners will meet if the linked list is looped. Depending on if the loop start at a odd or even point in the list the list count will be the number of steps the slow runner took up minus 1 to the point it is equal to the fast runner or step behind the fast runner.

class Node {
 Node next;
 int data;
}
int findLength(Node head) {
 if(loopedList == null)
  return -1;
 if(head.next == null)
  return 1;
 if(head.next.next == null)
  return 2;
 Node slow = head;
 Node fast = head.next.next;
 int count = 1;
 while(slow != null) {
  if(slow.equals(fast)){
   count--;
   break;
  }
  if(slow.next.equal(fast))
   break;
  slow = slow.next;
  fast = fast.next.next;
  count++;
 }
return(count)
}

Just store head node and compare with every next nodes with head node.
It's a singly linked list, so partially looped list is not possible. e.g. '1-2-3-4-3'.
Always, head node should be linked to the last node if it's a loop.

Solution 1:
If we are allowed to take extra space .. then we can use the hash_map and store all visited addresses and store it in the hash_map and increment the counter............. and then when node->next = any visited break the loop ... counter gives the length of the linked list .. o(n) time
Solution 2:
Add an additional element to the structure say add boolean visited ( instead of hashmap) we can check whether node->next == visited node break the loop return the counter

only one loop is possible in single linked list....
approach
1. find the starting node of the loop and find the number of nodes in loop
2. find the number of node between head node and starting node of the loop
3. add the result of 1 and 2..