CareerCup

1.Find whether you have the cycle. At the end of it you will have fast ptr = slow ptr
2.Find the length starting from the next node of the slow ptr to the slow ptr = length of loop
3. Find length from head node to slow ptr
4. These are basically two linked lists whose length we just found. Use their lengths to find common node.
4.1 Advance difference number of nodes in longer list and then start one node at a time in both lists till you hit the common node. That way you get the length till the common node.
5.Sum up the two lengths to find length of the entire list.

1. To find the length of loop:
Pointer A advances one node a time. Pointer B advanced two node a time. Start from head, they advanced at the same time until B hit null(no loop) or A and B point to the same node.
Now, has A advances only, A would meet B again. You can find the length of the loop say L.
2. Start from head again, this time have a pointer C advances L note first, followed by pointer D behind it, each advances one node at a time. When they meet, the number of nodes D traveled L0 plus L is equal to the length of the linked list with a loop.

How about setting up a hash table that would have references of each visited element in the linked list and then simply iterating through the linked list? Each time we are at an element we check if its reference is in our table and if not, we put it there and increment the element count. When we find that one of the elements has already been visited, we break the loop and return the element count.

Here is one solution. Not sure if anyone can come up with a better solution

node* detectloop(node* first) //Detects the loop in a given linked list
{
node *trav1, *trav2, *loopNode=NULL;
trav1=first;
if(trav1&&trav1->next!=NULL)
trav2=trav1->next->next;

while(trav1!=NULL || trav2!=NULL)
{
if(trav1==trav2)
{
loopNode=trav2;
break;
}
trav1=trav1->next;
if(trav2->next==NULL)
break;
trav2=trav2->next->next;
}
return loopNode;
}


long lengthOfLoop(node* first)
{
node *loopNode=detectLoop(first), *trav;
long count=0;
if(loopNode==NULL)
return count;
trav=loopNode;
while(trav!=loopNode)
{
count++;
trav=trav->next;
}
return count+1;
}

Is there a way we can format the code in here.

All the code what people post is so tough to read because of no indentation that just makes senseless. I hope Gayle is listening and may be can change the layout of site where we can put [CODE] and [/CODE] for indentation.

I would like to know to how many nodes a node can point to .. ie the number of pointers. if it was singly linked list then it would be a circular one.

In Linked list Node can point to only one node.
Example of Linked list with loop is
A=>B=>C=>D=>E=>F=>G=>C

Here is an O(n) algorithm.

Detect the start of the cycle using the slow pointer fast pointer method ---> O(n). Store the pointer of the cycle node in a temp.

Initialiaze a flag to 0;

Iterate through the list and check

while(head)
{
if (head-> next == temp && flag==1)
return count;

else if (head->next==temp)
flag=1;

count++;

head=head->next;
}

Total time complexity is O(n) which is the best you can do in this case.

Here is a solution.

Suppose we have a link list like this: The answer should be 5. So total length of the link list is length visited without loop + length of the loop.

a -> b -> c ->d -> e ->c

1. use slow/fast pointer to find if there is a loop. have slow pointer go around to find the length of the loop. Call it LEN_LOOP.

2. slow = head;
fast = /*points to the place where slow and fast met */
length = 0;
while(slow->next != fast->next){
slow = slow->next;
fast = fast->next;
length++;
}
return (length + LEN_LOOP;

Here is a solution.

Suppose we have a link list like this: The answer should be 5. So total length of the link list is length visited without loop + length of the loop.

a -> b -> c ->d -> e ->c

1. use slow/fast pointer to find if there is a loop. have slow pointer go around to find the length of the loop. Call it LEN_LOOP.

2.

slow = head;
   fast = /*points to the place where slow and fast met */
   length = 0;
   while(slow->next != fast->next){
         slow = slow->next;
         fast = fast->next;
         length++;
    }
    return (length + LEN_LOOP;

The slow and fast pointer meets in some node in the loop. So sum of nodes in loop plus the number of nodes till this node will give a number greater than the original number of nodes.
So, start of the loop is to be found by using one more pointer that moves from the head and is compared every time with all the nodes in the loop. When both are equal, we get the start of the loop. Now count the no of nodes.

Length of loop can be found out by :
Length of loop ll = FastPtr.length - SlowPtr.length

Since 2 ptrs are meeting at some node that is present int the loop. Once they meet, have 1 more ptr 'lenFinder' starting from HEAD, while slow ptr completing entire round of loop (i.e. it will perform 'next' operation ll times ) and each time compare with 'lenFinder' ptr. If slow ptr doesn't match with 'lenFinder' ptr,perform lenFinder -> next and increase the counter by 1. Continue rotating the slow ptr again and continue the process until there is a match.
Whenever there is a match, break,
length of list = ll + position at which 'lenFinder' met - 1.

lenFinder = HEAD;
nonLoopNodeCount = 0;
while(!found) {
  int count = length of loop;
  while(count != 0) {
    if(slowPtr == lenFinder) {
        found = true;
        break;
    }
    slowPtr = slowPtr -> next;
  }
  lenFinder = lenFinder -> next;
  nonLoopNodeCount++;
}
Length of list = nonLoopNodeCount + length of loop - 1;

Good logic mysolution.. works well :)

what about keeping the address of first node in some variable say ,"start" and then traverse the list and the same time increment the length and check the address with the "start"

sak you and your solution suck ! its vague and is not going anywhere, not even a partial solution, suck ^ N.

bool FindLengthAndPossibleCycle(Node *head, int *length)
{
	if(!head || !head->next)
		return false;
	Node *slowPtr = head;
	Node *fastPtr = head;
	bool hasLoop = false;
	*length = 1;
	do
	{
		if(fastPtr)
		{			
			fastPtr = fastPtr->next;
		}
		else
			break;

		if(slowPtr == fastPtr)
		{
			hasLoop = true;						
			break;
		}

		if(fastPtr)
		{			
			fastPtr = fastPtr->next;
		}
		else
			break;

		if(slowPtr == fastPtr)
		{
			hasLoop = true;						
			break;
		}

		if(slowPtr)
		{
			(*length)++;
			slowPtr = slowPtr->next;		
		}

	}
	while(true);
	slowPtr = slowPtr->next;
	while(slowPtr && slowPtr != fastPtr)
	{
		slowPtr = slowPtr->next;
		(*length)++;
	}
	return hasLoop;
}

a -b -c - d
| |
e - |


fastptr = a c e d fastptr pointing to d

slowptr = a b c d e

length = 1 2 3 4 5

The answer of my solution is correct. Kindly do not post other solutions which are inefficient.

O(n) solution :

1. Run the slow pointer and fast pointer algorithm. The point where you stop lets call it at node A.
2. Now get the two lengths like below:
2.1 - start from node A->next and come back to node A. Length = X.
2.2 - start from head and come to node A. Length = Y.
3. Now assume X > Y then calculate X-Y. Treat X as Y and v.v. if Y > X
3.1 - start from A->next go (X-Y) nodes further and mark is pointer m.
3.2 - start another pointer n from head and let pointer m and n go together they will meet at the node where the circle starts :) - yes they will. Lets say both of these pointers have traveled Z nodes.
3.3 - now length of the list = X + Y - (Y-Z) = X + Z.

Edit1:
Looks like this solution is already posted by "my solution" ...

1. run slow and first pointer algorithm and let P1 and P2 stops at a node A.( assuming startOne is the head of the list given)

2. break the list and create a start pointer  startTwo =  A->next; and  A->next = NULL; and keep P1 pointing to A.

3. Now find the lenth of two lists let as say L1 and L2. calcualte |L1-L2|

4. since P2 has no use, take P2 and one more new pointer P3.

5. Now lets say P2 = startOne and P3= startTwo

6. if L1 is greater move P2 to |L1-L2| times else move P3 |L1-L2| times.

6. now move P2 and P3 one one step ahead till both are same.let us say they moved m steps. 
 
7. Now Total number of nodes =  L1+m if L1 is bigger else =L2+m if L2 is bigger.

7. now make P1->next = startTwo to restore the list

Detect loop point
By (Slow pointer and fast pointer approach), find the loop detection node

Now take pointers P1 and P2, P1 at the loop detection node and P2 starting from head of the linked list
Traverse both the pointers one at a time
Both the pointers meet at the node because of which there is a loop in the linked list
------------
Use the standard fast and slow pointer algorithm find the loop detection point

Take two pointers P1 and P2 at loop detection point. Place pointer P1 at the same place and move P2 forward one step at a time. Repeat until both the pointers meet together. Keep a count variable incremented for every iteration which gives length of the loop. Let say the length is L1

Again take two pointers P1 and P2. P1 at the head of the linked list and P2 at the loop detection point. Forward both the pointers one step at a time. Repeat until both the pointers meet together. This procedure is equivalent to the one we use to calculate node that causes loop in a linked list. Keep a count variable incremented for every iteration which gives the length of the list until the merging point. Let say the length is L2
Now the length of the list that contains loop is L1+ L2

This is one way to find length of Linklist , where one reference jumping two place ahead.

public int lengthlist()
{
Node len=start;
int count=0;
if(len==null)
{
return 0;
}
while(len!=null&&len.next!=null)
{
len=len.next.next;
count++;
}
if(len==null)
{
return 2*count; // for even length list
}
else
{
return 2*count +1; // for odd length list
}
}