CareerCup

EDIT:
The previous algo failed for some input cases. Thanks to @ buckCherry for pointing it out. Below is the fresh algo.

Find the start of the cycle through Floyd cycle detection algorithm. The total number of nodes is the count of nodes that form cycle and count of nodes that are not part of cycle. If the list doesn't contain cycle, count of nodes that are part of cycle is zero.
1. Maintain two pointers called hare & tortoise.
2. move hare two steps & tortoise one step until either both become equal or hare reaches NULL.
3. Move tortoise to the start of the list. Move tortoise and hare step by step until their next node don't point to the same node( in case there is no cycle , hare will point to NULL. Ignore step#4 in this case). This next node is the starting node of the cycle. Meanwhile count the number of nodes that are not part of the cycle.
e.g. A->B->C->D->E->D
The number of nodes that don't form cycle is 3.

4. Count the number of nodes in the cycle. Start tortoise from the starting node of the cycle and keep on moving until it doesn't reach its initial position.
In the example explained in step#3, the number of nodes in the cycle is 2.

5. The answer is count in step#3 + count in step#4.

Traverse through the linked list. while traversing the linked list insert address(key) of each node into a hashmap.If it already exists in the hashmap then the linked list contains the loop. Maintain a counter to know the number of elements of the list while traversing..

Timecomplexity-O(n)

you can first find if there is cycle in linklist or not(Using 2 pointer floyd theorm) in O(n) time
(i)If it is present then that node(ie. start node for cycle) will be your check point.
while counting you need to look at.


otherwise it is a normal link list

you can first find if there is cycle in linklist or not(Using 2 pointer floyd theorm) in O(n) time
(i)If it is present then that node(ie. start node for cycle) will be your check point.
while counting you need to look at.


otherwise it is a normal link list

first check if der is a loop wid o(n) complexity floyds theorem..
if loop is der,mark the starting node of loop wid pointr p.now tak a pointr k pointing to first node of lnkd list.traverse it until u rech p,increment countr til dat.after dis loop,point k to the next sequential node.. again run loop and increment counter untill p is rechd.. counter is the no. of nodes we wanted..

such looping in list is solved using 2 pointers. one is ptr->next and the other is ptr->next->next. at 1 point they both meet and there your counting ends. when there is no looping you can just go to the end of the list incrementing the count.

such looping in list is solved using 2 pointers. one is ptr->next and the other is ptr->next->next. at 1 point they both meet and there your counting ends. when there is no looping you can just go to the end of the list incrementing the count.

such looping in list is solved using 2 pointers. one is ptr->next and the other is ptr->next->next. at 1 point they both meet and there your counting ends. when there is no looping you can just go till the end of the list incrementing the count.

such looping in list is solved using 2 pointers. one is ptr->next and the other is ptr->next->next. at 1 point they both meet and there your counting ends. when there is no looping you can just go till the end of the list incrementing the count.

in the question it is specified that we may be given a link list which may or may not have a loop , and it may not start from the head.
Now consider that we were given a list which does not cointain loop (singly linked list) and we did not start form the head , then starting from the point or node given to us there might be a possibility that there were nodes behind then how can we count them when finding the no. of elements in the list.

in the question it is specified that we may be given a link list which may or may not have a loop , and it may not start from the head.
Now consider that we were given a list which does not cointain loop (singly linked list) and we did not start form the head , then starting from the point or node given to us there might be a possibility that there were nodes behind then how can we count them when finding the no. of elements in the list.

LinkedListNode FindBeginning(LinkedListNode head) {
LinkedListNode n1 = head;
LinkedListNode n2 = head;

// Find meeting point
while (n2.next != null) {
n1 = n1.next;
n2 = n2.next.next;
if (n1 == n2) {
break;
}
}
// Error check - there is no meeting point, and therefore no loop
if (n2.next == null) {
return null;
}
/* Move n1 to Head. Keep n2 at Meeting Point. Each are k steps
/* from the Loop Start. If they move at the same pace, they must
* meet at Loop Start. */
n1 = head;
while (n1 != n2) {
n1 = n1.next;
n2 = n2.next;
}
// Now n2 points to the start of the loop.
return n2;
}

Here is an idea --

maintain three pointers:
a) head -- start of the given list
b) first -- jumps one step in iteration
c) second -- jumps two step in iteration

Start first and second pointers from the head and continue till both become equal (in case of loop) or second traverses the list completely and reaches the end(in case of linear list).

If the list is linear, number of nodes can be counted by traversing the list starting from head.

If the list contains a loop, notice the node where first and second becomes equal, store this new pointer tempPointer.

At this point, break the loop between tempPointer and tempPointer->next by using code below:

head2 = tempPointer->next;
tempPointer->next = null

Suppose the original list with loop was like:

head - a - b- c- d- e - f - g - h
| |
l -k - j - i

Suppose the loop is broken between f and g and null pointer is introduced:

then g becomes head2 and f->next is set to null:

head - a - b- c- d- e - f --> null
|
l - k - j - i - h - g (head2)

now we can traverse from head to null (first list)
and head2 to null (second list)

These two lists are merged at node e.

Count the number of nodes in first list -- count1
Count the number of nodes in second list -- count2

suppose count1 is greater than count2 (take whichever is greater)

then traverse first list by (count1 - count2) starting from head.
Then start traversing two lists together till you reach at merging point. Suppose you traverse M nodes together to reach merging point.

Then traverse the merged list.

The sum of nodes in both lists = number of nodes in first list + M

how cycle is detected using hare & tortouse algo?? can u please explain??

Mark the nodes and then count

Find the loop using floyd's algo,
then clacualte thenumber of nodes in the loop by fixing one pointer inside the loop and shifting another pointer in the loop untill bth of them become equal again, lets the number be m
now take a pointer pointing to the head and go to mth node now move the pinter to the head and the pointer pointing to the mth node step by step until the bcome equal and now you the node at which the loop starts

Using double pointers only, will not solve this problem. There two types elements in the list; first are say, X which are not in loop and other say, Y, which belongs to loop.
let number of X are x. and number of Y are y.
And we need to calculate the x + y.

I will go with this approach:
First reverse the linked list and increment a counter, counter will be give you the value of 2x + y.
Now, using floyd cycle detection algo to find any Y. Calculate the value of y by just traversing the loop once starting from Y.
Calculate x + y, using prior equations.
Reverse again the linked list to give its original shape.
Total complexity should be O(n).

What exactly does "may or may not start from the head mean" ??
We certainly cannot backtrack in a singly linked list unless its circular.
Maybe i am not clear with the question. Please explain.

'shodnik' and 'Anonymous' have already provided solutions which I'm not fully convinced untill I receive some response against my asks to them.
In the mean time here is my solution in O(n) time and with fixed additional memory.
The only drawbacks of my algorithm is that it requires changing the structure of the list whereas both of the solutions from them does not. Note that the solution given by 'Anonymous' does a change of list structure but it can be avoided.

Anyway here is mine.

Use Robert W. Floyd's cycle detection algorithm with slight augmentation to determine if there exists any loop and if so then is there any self loop
If there is no loop
     count length of the list
     return length
else if there is any self loop
     break the self loop by pointing to null
     //i.e. a list head->A->B->B wud become head->A->B
     count length of the list
     return length
else
     invoke countNode with head of the list
end-if


countNode(Node head)
     if h==null or h->next null
          return 0;
     end-if
     Node firstNode=null;
     Node t=h->next;
     while t!= null
          Node t_dash=t;
          t=t->next;
          t_dash->next=null;
          prepend(firstNode, t_dash);
     end-while
     return length(firstNode) -1 ;
end-function

prepend(Node firstNode, Node toAdd)
     if firstNode==null
          firstNode=toAdd;
          return ;
     end-if
     Node temp=firstNode;
     firstNode=toAdd;
     firstNode->next=temp;
end-function

Node slow = head;
	Node fast = head;
	while (slow != null && fast != null && slow != fast){
		slow = slow.next;
		if (fast.next== null)
			break;
		fast = fast.next.next;	
	}
	int size = 0;
	if (slow == null ||fast == null || fast.next == null){ // there is no loop
		Node temp = head;
	
		while (temp != null)
			count++;
		return count;
	}
	//now we want to find the head of the cycle
	slow = head;
	while (slow != fast){
		slow = slow.next;
		fast = fast.next;
	}
	//now fast/slow is the head of the loop
	Node current1 = head;
	Node current2 = slow.next;
	while (current1 != slow){
		size++;
		current1 = current1.next;
	}
	while (current2 != slow){
		size++;
		current2 = current2.next;
	}
	return size + 1;
}