Shreyas
BAN USERHere is a solution I think will work: have used slow and fast pointer to find the loop first then to count the number of nodes.
public int nodeCount(LinkedLists node){
LinkedLists slow=head;
LinkedLists fast=head;
while(fast!=null && fast.next!=null) {
slow = slow.next;
fast = fast.next.next;
if(slow==fast) //both pointers have collided
break;
}
//Check if there are no loops at all
if(fast==null || fast.next==null)
return 0;
// Now move slow to head, and increment slow and fast by one step so that they meet at the loop/cycle beginning point.
slow = head;
int countk = 0;
while(slow!=fast) {
slow = slow.next;
fast = fast.next;
countk++;
}
//Now keep the slow pointer there and increment fast pointer by 1, when slow==fast u have counted the entire list
fast = fast.next;
countk++;
while(slow!=fast) {
fast = fast.next;
countk++;
}
return countk;
}
If we can use extra memory, then using hashmaps we can do it. For each element we add hash(array[i])=1; and whenever we find containsKey(array[i])..we delete it so that at the end of scanning all the elements in array in hashmap we will be left with only one element.
If he asks for 2 or more, then all the remaining elements in the map are unique.
consider this example:
- Shreyas February 21, 20121->2->3->4
and x is 2
you code does this:
1->3->3->4 (node->data = node->next->data;)
1->3->4 (node->next = node->next->next;)
1->3(delete node.next)// this particular line is not required according to me.